（运筹学与控制论专业论文）图的l（st）标号数与边跨度.pdf

摘要 图的l ( 2 ，1 ) 标号是从频道分配问题中概括出来的一类图的着色问题假定某一地区有 若干电台，这些电台要在给定的频道内传输信号为了减少干扰，。相邻”的电台必须使用相 差足够远的频道，“邻近。的电台必须使用不同的频道我们要在互不干扰的前提下使用最 少的频道资源对每个电台分配频道一般地，设s 和t 是两个非负整数，图g 的一个二( 8 ，t ) 一 标号是从g 的顶点集到整数集的映射，满足；( 1 ) l ，( u ) 一，( ) i s ，如果w e ( g ) ；( 2 ) i f ( u ) 一，( 口) i t ，如果d ( “，口) = 2 图g 的l ( 8 ，t ) 一标号数定义为m i n ! m a x f ( v ) ：口y ( g ) h 记为a 襻，。( g ) 最初的关于工( s t ) 一标号的文章主要是研究8 t 的情况，然而，某些实际 问题却涉及到s t 的情况比如在处理隐终端干扰问题时，b e r t o s s i 与b o n u c e u i 引入并研 究了图的l ( 0 ，1 ) 一标号为了避免两种类型的干扰，x i a oh u at e r e s a 与r o g e rk y e h 提出 了图的l ( 1 ，2 ) 一标号进一步，本文研究了它们的一般情况即sst 时图的l ( s ，t ) 一标号在 第二部分中我们给出了路、圈与轮的8 t 时的l ( s ，t ) 一标号数 设8 和t 是两个非负整数，给定图g 的一个l ( s ，t ) 标号，的l ( s ，t ) 一边跨度定义为 m a x i f ( u ) 一，( ) l ：( “， ) e ( g ) ，记为风j ( g ，f ) 图g 的l ( 8 ，t ) 一边跨度定义为m i n 凡t ( g ，f ) ： ，取遍图g 的所有l ( 8 ，t ) 标号) ，记为岛。t ( g ) 设丁是一颗最大度为( 2 ) 的树在第三 部分中我们证明了：若2 s 2 t 0 则3 , , t ( r ) = ( f 2 1 一s ) t + s ；若0 2 s t 且是偶数， 则风t ( t ) = ( 一1 ) 2 t ；若0 2 s t 且为奇数，则凡t ( = ( a 一1 ) t 2 + s 同时本文 完全确定了两条路的笛卡尔乘积图和正四边形网格的l ( s ，t ) 一边跨度并且研究了圈与k 一 部完全图的l ( s ，t ) 一边跨度 关键词；频道分配问题，l ( s t ) 一标号，两条路的c a r t e s h n 积，正四网格，上( 毛t ) 一边跨度 a b s t r a c t t b e l ( 2 1 ) - l a b e l i n g o f a g r a p h w a s m o t i v a t e d b y a s p e c i a l k i n d o f c h a n n e la s s i g n m e n t p r o b l e m s u p p o s ean u m b e ro fb r o a d c a s t i n gs t a t i o n sa x eg i v e n t h e s es t a t i o n sn e e dt r a n s m i ts i g n a l st h r o u g h p a r t i c u l a rc h a n n e l s i no r d e rt or e d u c et h ei n t e r f e r e n c e ，a n yt w o v e r yc 1 0 6 e s t a t i o n sm u s tr e c e i v e c h a n n e l sa p s f f te n o u g h ，a n da n yt w o c l o s e s t a t i o n sm u s tr e c e i v ed i f f e r e n tc h a n n e l s w ew a n tt ou s e t h el e a s tc h a n n e lr e 6 0 u r c et oa s s i g nc h a n n e l st oe a c hs t a t i o ns u c ht h a tt h ei n t e r f e r e n c ei sa v o i d e d i ng e n e r a l ，f o ra n yt w on e n n e g 矗, t i v ei n t e g e r s8a n dt ，a nl ( 8 ，t ) 一l a b e l i n go fag r a p hg ，i sam a p p i n g f ，f r o mt h ev e r t e xs e ty ( g ) t on o n n e g n t i v ei n t e g e r s ，s a t i s f y i n g ：( 1 ) i ，( 让) 一，( 口) i 8 ，i f 删e ( g ) ； ( 2 ) i f o ) - f ( v ) i t ，i f d ( u ，口) = 2 t h e l ( 8 ，t ) 一l a b e l i n g n u m b e r o f a g r a p h g ，a ，脚，i ( g ) ，i s d e f i n e d a s ，m i n fm a x f ( v ) ：口y ( g ) ) e a r l yp a p e r so nl ( 8 ，t ) 一l a b e l i n g so fg r a p h su s u a l l ys t u d i e dt h e c a s eo2t h o w e v e r ，8 0 m ep r a c t i c a lp r o b l e m si n v o l v el ( 8 ，) 一l a b e l i n go ff 印h sw i t h8 t f o r e x a m p l e ，t od e a lw i t ht h eh i d d e nt e r m i n a li n t e r f e r e n c ea v o i d a n c ep r o b l e m ，b e r t o e s ia n db o n u c e l l i i n t r o d u c e da n di n v e s t i g a t e dl ( o ，1 ) 一l a b e l i n go fag r a p h ；a n dl ( t ，2 ) - l a b e l i n go fag r a p hw a sp u t f o r w a r db yx i a oh u at e r e s aa n dr o g e rk y e hi no r d e rt oa v o i dt w ot y p e so fc o l l i s i o n s m o t i v a t e d b yt h e s ep r o b l e m s 。t h i st h e s i si n v e s t i g a t e st h eg e n e r a lc a s eo fl ( 8 ，t ) - l a b e l i n g so fg r a p h sw i t h8s t r e s u l t so nl ( 8 ，) 一l a b e l i n gn u m b e r sw i t h8 to fp a t h s ，c y c l e sa n dw h e e l sa x ep r e s e n t e di ns e c t i o n 2 s u p p o s e8a n dta x ea n yt w on o n n e g a t i v ei n t e g e r s g i v e na nl ( 8 ，t ) 一l a b e l i n gfo fag r a p h g ，d e f i n et h el ( 8 ，t ) 一e d g es p a no ff ，岛，t ( g ，f ) t ob em a x l f ( u ) 一，( ) i ：( “，口) e ( g ) ) t h e l ( 5 ，t ) 一e d g es p a no fg ，风( g ) ，i st h em i n i m u ml ( 8 ，t ) 一e d g es p a no f ，w h e r et h em l n i m u i nr u n s o v e ra l ll ( 8 ，t ) 一l a b e f i n g sfo fg l e ttb ea n yt r e ew i t hm a x i m u md e g r e ea 2 i ns e c t i o n3 ， w es h o wt h a t ，i f2 8 t 0t h e n 风( t ) = ( r l x l 2 1 1 ) t + 8 ，i f0 2 8 5 = 睢；或。 ，_，、liiiiii、 东南大学顿士学位论文 定理1 2 1 4 4 1 设8 2 t ，令g 为包含n 个顶点的圈则有 圳耻巨善 定理1 2 1 5 1 4 1 设t 曼8 2 t ，令g 为包含n 个顶点的圈则有 b c 耻r 嘉 工( 。，t ) - 标号相对于l ( d ，1 ) 一标号在研究中给我们又增加了些困难很多图类即使我们得 到了l ( 2 ，1 ) 一标号数，也很难得到l ( d ，1 ) 一标号数或l ( s ，t ) 一标号数过去十几年中，l ( 2 ，1 ) 一 标号的研究相对来说已经比较丰富l ( d ，1 ) 一标号和l ( s ，t ) - 标号的研究还有很多空缺之 处，其原因主要在于问题的难度加深了但是，由于 t a l s t j ，l ( g ) = 【。”，t ( g ) a - t ( g ) 九摹，t 1 ，t ( g ) = 七a 卜t ，l ( g ) 如果知道了图g 的l ( s ，1 ) - 标号数，我们便知道了g 的l ( s ，t ) 一标号数的上下界，有助于进 一步研究图g 的l ( s ，t ) - 标号数 图g 的l ( s ，t ) - 标号0 t ) 的某些特殊情况如下t 定理1 2 1 6 旧 f0 ，l ：2 知，l ( r ) = 【1 n 3 f1n ：2 a 1 ，1 ( r ) = 【2 n 3 f a l ，2 ( r ) = 【 n = 2 n = 3 n 4 6 1 2 3 定理1 2 1 7 1 7 1 知1 ( c j ) = a 1 1 ( g ) = 0 竹= 3 1 t l ；o ( l o d 4 ) 2 其他 2 n ；o ( t r m d 3 ) 4 竹= 5 3 其他 椰= i 暑c 一， 岛1 ( p 丌。晶) = 如，l ( 口) = 3 ，n m 1 触l ( 晶r ) = 国1 ( 口) = d + 1 ，这里n m 1 1 4 本文的主要工作 本文主要研究了路，圈和轮的l ( s ，) 一标号问题( 这里8 t ) ，同时探讨了树，路乘积 图，正四网格以及圈和“部完全图的l ( s ，) 一标号的边跨度 在第二章中，我们在路，圈，轮的l ( o ，1 ) - 标号，l ( 1 ，1 ) 一标号以及l ( 1 ，2 ) - 标号的基 ，llli-llll，_ll-lll 翻朝 组 盟 2 2 l l 理理 定定 一 d 东南大学硬士学位论文 8 础上，进一步给出了它们的z ( s ，t ) - 标号0 t ) 得到如下的结果t1 当s t 2 时，有 。( 局) = t ，a s , t ( r ) = 。+ t ，n 24 ) 当t 2 8 t 时，有x , t ( e s ) = 2 s ，九t ( p 4 ) = k ，t ( r ) = k j ( r ) = 8 + t ，k # ( r ) = m i n 3 s ，2 t ( n 7 ) 2 当8 t 2 时，有 。j ( 伤) = 2 s ，x o , t ( g ) = 8 + t ( nio ( m o d 4 ) ) ，k 。t ( g ) = 2 t ( 其他) ；当2 t 3 8 t 时，有k t ( c s ) = 2 s ，n 3 时有 儿t ( g ) = 2 t ( nio ( m d 3 ) ) ，k t ( 6 5 ) = 如，k ，t ( g ) = 3 8 ( 其他) 当t 2 8 2 t 3 时，有 x , t ( c s ) = 2 s ，n 3 时有，t ( g ) = 3 s ( n o ( ”州4 ) ) ，t ( c 5 ) = 如，a 。( c ；) = 2 t ( 其他) 3 当 t 2 j t 时，有) t s , t ( = 当t 3 8 s t 2 时有a a , t ( ) = 3 s + 似一3 ) t 9 ，n 为奇数， “( w 0 ) = 如+ ( ( n 2 ) 一2 ) t ，n 为偶数当8 t 3 时，有a s , t ( 矸0 ) = 加一1 ) t 2 ，n 为奇数， “( ，n ) = o + ( ( n 2 ) 一x ) t ，n 为偶数 在第三章中，我们完全确定了最大度为的树的l ( s ，t ) 标号的边跨度( 22 ) ，并 由此得到了路乘积图和正四网格的l ( s t ) 一边跨度1 得到了。1 当8 t 2 ，t 0 时，有 风t ( t ) = ( 2 1 ) t + 彤当0 s5 t 2 ，a 为偶数时，有风，t ( t ) = f ( 一x ) t 2 ；当0 s t 2 ，a 为奇数时有风，f ( t ) = ( 一x ) t 2 + 8 2 当2 0 之t 时，有岛t ( p 竹。r ) = 0 0 1 ( 口) = 8 + t ；当 知 t 时，有岛t ( p m 晶) = 岛1 ( 口) = f s t 2 并探讨了圈及女一部完全图的边跨度 1 投稿于东南大学学报( 英文版) ，见文【16 】 第二章路、圈、轮的l ( s ，) 一标号数( s t ) 在文 4 1 中给出了s t 时n 个顶点的路与圈的工( t ) 标号数，( 见定理1 2 1 2 - 定 理1 2 1 5 ) ，在文【7 l 中，给出了 个顶点的路、圈和轮的工( 8 ，t ) - 标号数，这里8 t 并且 8 ，t = 0 ，1 ，2 ( 见定理1 2 1 6 - 定理1 2 1 8 ) 下面我们以这几种特殊情况为基础来研究n 个顶 点的路，圈和轮的l ( s ，t ) - 标号0 f ) 下面我们给出一个引理，它是我们研究图的l ( s ，t ) 一标号的基本工具 引理2 1 1对所有的图g ，都存在个l ( s ，) 标号满足每个顶点的标号都是5 与t 的 线性组合( 即具有+ 肛的形式，n ，卢为非负整数) ，特别地存在某个非负整数a ，反使得 。t ( g ) = + 肛 在文【4 】中已有此定理的s2t 的情况，本引理的证明与它类似 2 1 路的l ( s ，t ) 一标号数 定理2 1 2 设晶为含有n 个顶点的路，且s ，则有 “( r ) = 件= 1 n = 2 n = 3 + tn24 证明：对n 3 时的情形易证下面只证明n 4 的情形设r = 口1 也，一方面， l3 + ti 0 ( m o a4 ) 给r 一个标号，满足，m ) ： 0 i 5 “甜4 ) 易证，是个工( 8 t ) 一标号，其跨度 l s i = 2 ( r o o d4 ) 【t i ；3 ( m o a4 ) 为s + t ，故a “( r ) s + t 另一方面，设t 4 = ly 2 姐u 4 ，下面证明九t ( 局) s + t ，对只的任一 个l ( 最t ) 一标号g ，如果m i n g ( v 2 ) ，9 ) = 0 ，不妨设g ( u 2 ) = 0 则m g ( 1 ) ，9 ( ) ) s + t 即 有a s , t 旧) s + t 如果厕n 如( 1 ) ，9 陬) ) = 0 ，不妨设9 ( v 1 ) = 0 若 e 9 ( 睨) ，9 ( 地) s + t ， 则有a 。t ( t 4 ) 2s + t 否则由9 忆) s 知9 m ) 9 ) 一t 3 + t t = s ，由引理2 1 1 知g ) = 0 ，从而必有m n z f g 池) ，9 似) ) 8 + t ，即a ( 只) s + t ，因而我们得到 a “( r ) a s ，( j ) 4 ) s + t 由以上两个方面知a ( r ) = s + t ( n 4 ) 东南大学硕士学位论文 定理2 1 3 设r 为含有n 个顶点的路，且 8 t ，则有 。j ( r ) = o 2 s 粤+ t m n 轴，2 t 竹= 1 n = 2 n = 3 4 ，l 2 t 时。可给r 另一 i 嚣 i io ( m 。d3 ) 个标号9 ，使g ( 饥) = 0 i i1 ( r o o d3 ) 易知9 也是一个l ( 乳) 一标号，其跨度为2 t ， i ti i2 ( m o d3 ) 故a “( r ) s2 t ， 由以上的证明可知a “( r ) r a i n a s ，甜) 另一方面，当3 s 2 t 时，下证凡t ( 马) 3 s 用反证法假设a ) 3 s ，则一定存 在一个整数标号f 其跨度小于孙于是有i ( v i ) 0 ，s ，t ，2 s ，s + t ) ，i = 1 ，2 ，3 ，4 ，5 ，6 ，7 由对称 性，如果f ( v 1 ) = 0 ， ( 1 ) 若，池) = s ，则i ( 3 ) 2 s ，5 + t ) ，y ( v 4 ) 2 8 ，s + t ) ，从而i f ( v 3 ) 一i ( v 4 ) i t 一8 s ， 矛盾； ( 2 ) 若，( t j 2 ) = t ，则y ( v 3 ) = s + t ，i ( v 4 ) = 0 ，y ( v 5 ) = 8 ，( t j 6 ) 2 8 ，8 + 螗，( 研) 2 8 ，s + t ， 从而i f ( v 3 ) 一f ( v 4 ) i t 一8 s ，矛盾； ( 3 ) 若，池) = 2 s ，则f ( v 3 ) o ，2 s ，s + t ) 从而l f ( v 3 ) 一i ( v 2 ) is t s 8 ，矛盾； ( 4 ) 若，池) = s + ，则f ( v 3 ) = t ，f ( v 4 ) = 0 ，f ( v 5 ) s ，2 s ，5 + t ) ，从而i i ( v 3 ) 一f ( v s ) i t ， 矛盾； 如果i ( v i ) = 0 ，i = 2 ，3 ，则m ，m 1 ) ，i ( v i + 1 ) 8 + t ，若l ( v l + 1 ) = s + t ，类似于上面 东南大学顼士学位论文 ( 4 ) 的证明可知i ，( 仇+ 2 ) 一，( q + 4 ) i t ，若，似一1 ) = s + t ，则f ( v l + 1 ) = s ，类似于上面( 1 ) 的证 明可得l f ( v l + 2 ) 一，( 仇+ 3 ) l t 一5 5 ，若，h ) = 0 ，则m i n f ( v 3 ) ，) = 8 ，同理可证于是 我们得到儿。t ( 马) 孙 当抽2 t 时，类似于上面的证明同样可以得到k t ( b ) 2 t 从而我们得到a 。 ( 晶) 2 a j ( 岛) 2m i n 3 s ，哪 由以上两个方面我们便证嘎了九t ( r ) = m i n 3 s ，2 t ) 伽7 ) k c 啦净t ， 证明：易证 “( c s ) = 2 s ，当n ! o ( d 4 ) 时，设g = ”l 抛一方面给g 一个标 乳刚加 0 + ti i0 ( m o d 4 ) i 5 1 ( ”。d 4 ) 易知f 是一个l ( s ，t ) 标号，其跨度为8 + t ，从而 ii2 ( m d 以) i ；3 ( m d 以) s + t 0 另一方面，对g 的任一个标号9 ，由对称性，不妨设g ( v x ) = 0 ，则m a z g ( v n ) ，9 ( 忱) s + t 故( g ) 8 + t 综合知a ( g ) = s + t 奎童查兰堡圭兰堡堡塞 1 2 n o ( m o d4 ) 下证。t ( g ) = 2 t ，设g = 口l ，t j 2 ，先给g 一个标号 满足 n i l ( r o o d 4 ) 时，慨) = 0 + t o s t 甜 i o ( m d d4 ) i e1 ( m 甜4 ) i ；2 ( m o d4 ) l ；3 ( m o d4 ) 0 s t0 s ts + t n ：2 ( m o d4 ) 时，) = s + ts + tt 8 0 i o ( t 7 捌3 ) 且i 6 l e l ( m d d3 ) 且i 6 i e2 ( r o o d3 1 且i 6 i eo ( m o d4 ) 且i 7 i i l ( r o o d4 ) 且i 27 t = 2 ( m o d 4 ) 且i 7 i i3 ( m o d4 ) 且i 7 0 t 2 t0 t2 t0 口 2 tt 0 2 t t0 射 o 。 o 卧甜 。 东南大学硕士学位论文 n ；3 ( r o o d 4 ) 时，觚) = i ：o ( m o d4 ) l i l ( m o d4 ) i i2 ( m o d4 1 i e3 ( r o o d4 1 i = n 一2 i = n 一1 8 08 + tt b + t 2 t s s 0 s + tt 8 0 s + tt s + t 易验证，是一个l ( 8 ，t ) 一标号，且其跨度为2 t ，从而a “( g ) 2 t 另一方面，由定理1 2 9 知： 州( g ) 知，t ( g ) = t a o , l ( g ) = 2 t 由以上两方面可知a “( g ) = 2 t 。 8 o 8 甜 卧 东南大学硬士学位论文 定理2 2 2 设g 为t 1 个顶点的圈，当争s5 t 时有 - 。c c k ，= 圣要m d d 3 ) 王in 3 证明：易证九。t ( 岛) = 当n ；o ( m o d 3 ) 时，一方面我们给g = t ，l ，地，个标号， f 2 t i = - - o ( m o d3 ) 满足，似) = 0i i l ( n m d3 ) ，显然，是一个三( s ，班标号，其跨度为2 t ，故 ( g ) 2 t 【t = 2 ( m o d3 ) 另一方面，当n = 6 时，设侥= 口1 ，t ，2 ，用反证法证明a s , t ( 岛) 2 t 否则若a s , t ( 瓯) 盘。由引理2 1 ，i 知存在一个整数标号，它的跨度小于勉，即跨度为8 + t ，不妨设f ( v 1 ) = 0 ，) = 5 ，池) = 5 + t ，则f ( v 4 ) m z 8 + t ，5 + 甜 矛盾而当n 9 时，g 中一定有一 个导出子图竹，于是a s , t ( g ) a s t ( 厅) = 2 t 当n = 5 时，一方面1 ( 岛) 1 “( 如) = s a t ，1 ( 岛) = 4 s 另一方面给c s = 口l ，t j 2 坞各 顶点依次标号为：0 ，s ，2 s ，3 8 ，4 s ，显然它是一个l ( 毛咖标号，其跨度为4 s ，故a 。( g ) 4 s ， 由此两方面可得a “( g ) = 4 s 当n 5 且n o ( 粥) 时，一方面凡，i ( g ) k 。( g ) = s a t ，l ( g ) = 3 s 另一方面，给g = l ，忱以下标号，满足。 当n e l ( m o d3 ) 时，( ) = 2 tt i0 ( m o d3 ) 0 i 1 ( r o o d3 ) ti e2 ( m o d3 ) 0 i = f l 一3 si = ，l 一2 2 ai = n 一1 3 si = n 0 s 0 s 2 s 3 s li 3 s2 s2 t0 1 4 奎童奎兰堡圭兰堡垒壅 ” 0t2 t0 t2 t 当n = 2 ( r o o d3 ) 时。，慨) = 0 s s 3 s i 0 ( r o o d4 ) 且l 8 0 i i l ( r o o d 4 ) 且i 8 8 i = 2 ( m o d4 ) 且i 8 知 i 3 ( m o d4 ) 且i s8 0 o ( t ，l o d3 ) 且i 9 t t i l ( r o o d3 ) 且 9 2 t 2 ( r o o d3 ) 且i 9 0 s 2 s3 s 3 s 2 s o 2 s s 0 3 s0 s 2 s3 s 2 tt0 2 t0 容易验证以上标号，均是l ( s ，) 标号，且其跨度为3 s ，故九，t ( g ) 3 s 由此两 奎童奎兰堡圭兰堡垒兰 1 6 方面知a d c ) = 3 s 定理2 2 3 设g 为n 个顶点的圈，当 5 争时有 f3 8 k ( g ) ： 缸 l 就 n ；0 ( m o d4 ) 竹= 5 其他 ( c 3 ) = 2 s ，当，l i o ( ”1 0 d4 ) 时。设g = l 地一方面给g 个标 i i o ( m o d 4 1 注1 ( m o d 4 ) 易知f 是个l ( s , t ) 标号，其跨度为3 s ，故a 。j ( g ) s3 s i ；2 ( r o o d 4 1 i i 3 ( m d d4 ) 另一方面，a j , t ( g ) a o m c ) = 3 a 1 2 ( g ) = 3 s ，综合知a j ( g ) = 3 s 而对岛仿上面 的定理类似可证明 当n o ( m o d4 ) 且n 5 时，一方面， 蚶( g ) = ；b ，( g ) ；a t 盘( g ) = a 1 ，2 ( g ) = 4 = 2 t 另一方面给g 一个标号f ，满足： 当n ；l ( m o d4 ) 时，( ) = 2 ti io ( m o d3 ) 且 s9 0 i ；1 ( r o o d3 ) 且l 9 t i 2 ( r o o d3 ) 且t 9 8 i = 3 ( r o o d4 ) 且 1 0 2 si io ( m o d4 ) 且i 2 1 0 2 t i e l ( m o d4 ) 且i 2 1 0 0 = 2 ( m o d4 ) 且t 1 0 0t2 to o 2 t k 拈o 。知 证，l j l l 0 剔 卜 明 “ 证 使争 奎童奎兰堡圭兰堡堡塞 1 7 0t2 t0t2 t0 2 t2 s s 02 t t 当n 12 ( r o o d4 ) 时，m ) = 2 t l i 0 ( m 甜3 ) 且i s 6 0 i 1 ( r o o d3 ) 且i s6 ti e2 ( m o d3 ) 且i s6 0i es ( m o d4 ) 且i 7 毒 i 毫0 ( t ，l o d4 ) 且 7 2 s t i l ( n o d 4 ) 且i 7 2 ti i2 ( m d d 4 ) 且i 7 0 k2 k0t2 t0t2 t 口 2 kk 0 2 t2 s 8 0 当t l ；3 ( r o o d4 ) 时，f ( v 1 ) = 2 t i o ( m o d4 1 0 i = l ( m o d 4 、 8i 12 ( , n o d4 、 2 si ；3 ( r o o d4 、 0i = n 一2 ti = n 一1 2 t=n 壅童奎兰堡圭兰堡丝塞 1 8 0 s 2 s2 t 0 可以验证，是一个l ( s ，t ) 一标号，其跨度为2 t ，于是我们有1 ( 瓯) s2 t 从而由以 上两个方面可知 ，o ( g ) = 2 t 2 3 轮的l ( s ，t ) - 标号数 定理2 3 1 设w 0 是一个轮，当8 t 时，有儿，t ( h 0 ) = 证明；一方面a “( “名) k ，。( b i n ) = s a l 1 ( _ 【1 0 ) = n 8 另一方面。给h 0 = v ov 岛一个标号，其中g = 1 ，u 2 ，满足，( ) = 毛f ( v 1 ) = 0 ，( v d = i $ ，t = 2 ，3 ，一，n 5 s如6 8 5 s4 s 0 2 s3 s0 2 s 3 s 易知，是w 0 的一个l ( s ，) 标号，其跨度为n s ，从而有a “( 0 ) n s 因而由此两方面 东南大学硬士学位论文 我们证明了a “( 矸0 ) = m 定理2 3 2 设矸，n 是一个轮，当8 s 时，有 ：。，、j3 s + 2 尹t n 为奇数 凡 t 卜i 妇+ ( 玉。磊蒜 证明：当为奇数时，对w n 任一个标号，若，( 啦) = o 不妨设，h ) 5 为圈上各顶 点标号的最小者，则，r m z ，m ) ，) 2 s + t ，不妨设，她) = 2 s + t ，则以v o 为根，以 t j 2 ，m ，一1 为叶子的树的最大标号至少为s + t + ( 2 尹一1 ) t 3 s + 堡尹t ( 这是因为除地 外，所有的叶子与1 的距离均为2 ，故最小的标号至少为8 + t ) 若，) 0 ，设，) = x o ，且g 的顶点中有i 个顶点的标号比x o 小，那么：( 1 ) 当i 为奇数时，则最小的标号至多为：知一8 一警t ，而最大的标号至少为踟- 4 - 8 + ( 2 一1 ) t + 3 ， 教h o 的工( 8 ，t ) 标号的跨度至少为x o + s + ( 字一1 ) t + s 一( x o - - 8 - - 孚t ) = 3 s + 孚t ( 2 ) 当i 为偶数时，则最小的标号至多为tx o 一8 一气- - ? t s ，而最大的标号至少为x o + s + ( 譬笋) t ， 故的l ( s ，t ) 一标号的跨度至少为x o + 8 + ( t n - - i - - 1 ) t 一( x o s 一等t s ) = 3 8 + 学t 由以 上讨论可知k t ( 矸0 ) 3 s + 2 笋t 另一方面，给矸，n 一个标号，满足f ( v o ) = 2 j ，f ( v 1 ) = 0 ，他) = 8 ，f ( v 3 ) = 3 s ，h ) = 缸，似) ： 3 8 + 孚沩奇数且5 i4 s + 譬t 沩偶数且i 6 3 s + t 4 s 如+ t3 6 + t , i s 0 s 3 s03 s 易证，是矸。的一个l ( 8 ，) 一标号，其跨度为3 s + 2 尹，即九，l ( 矸，n ) 3 8 + 2 尹t 由以上两方面知a “( w ，n ) = 3 s - i - 2 笋t 下面证明t , 为偶数的情形对0 任一个标号，若f ( v o ) = o ，不妨设，( ) 8 为圈上 1 9 各顶点标号的最小者，则对3 一圈r o y l t ，2 来说，他) 2 s ，于是以v o 为根，以t ，2 ，m ， 为叶子的树其最大标号至少为知+ ( 2 1 ) t 24 s + ( 2 2 ) t 若，) 0 ，设，( 咖) = z o ，且g 的顶点中有i 个顶点的标号比知小，那么：( 1 ) 当 为 奇数时，则最小的标号至多为：知一5 一孚t ，而最大的标号至少为z o + 8 + ( 苎= 一1 ) t ，故h o 的l ( 3 ，t ) 标号的跨度至少为知+ 。+ ( 2 = 产) t + 8 一( 知一8 一孚t ) = 2 。+ 2 手t 钿+ t + ( 一2 ) t2 4 s + ( 一2 ) t ( 2 ) 当 为偶数时，则最小的标号至多为tx o 一8 一譬t 一8 ，而最大的标号至少 为z o + 8 + 2 产件毛故h o 的l ( s ，t ) 标号的跨度至少为知+ s + 4 2 产) t + 8 一( 知一8 一警t s ) = 4 s + ( 2 2 ) t 由以上讨论可知，t ( ) 4 s - i - ( 一2 ) t 另一方面，给w n 一个标号，满足，) = 2 s ，l ( v 1 ) = 0 ，f ( v 2 ) = s ，f ( v 3 ) = 3 s ，f ( v 4 ) = i3 s + 譬t 沩奇数且 5 如慨2 14 5 + 警t 为偶数且f 6 。 如+ t3 s + t 4 s 0 s 3 s4 s 易证，是w n 的一个l 小怀号，兵野发为4 s + ( i 一2 ) t ，e pa s ，t 【w n j s4 s + 【i 一2 ) t 由以上两方面知几，f ( h 0 ) = 4 s + ( ；一2 ) 定理2 3 3 设o 是一个轮，当s s ；时，有 一，= ；一1 ) t 茹萋【s + ( 2 一 n 为偶数 证明：当n 为奇数时，一方面，a 球( w 名) x o , t ( h o ) = t a o ，l ( o ) = 【2 尹j t = 2 尹，另一 方面，给峨一个标号，满足，= 。s ，m ，= 姜：；一。h ：舅翥萋 东南大学硬士学位论文 2 ts + ts + 2 t2 t s + t 0 8 0 8 易证，是w 的个工( 毛t ) - 标号，其跨度为4 尹，即a ( h ) s2 尹t 由以上两方面知a ( - ) = 8 t 当n 为偶数时，对矸0 任一个标号若f ( v o ) = 0 ，不妨设，( ”1 ) 28 为圈上各顶点标 号的最小者。则以t j 0 为根，以1 1 1 ，t j 3 ，一1 为叶子的树的最大标号至少为8 + ( 2 一1 ) t ； 若f ( v o ) 0 ，不如设，( 1 ) = 0 ，则，池) s ，则以v o 为根，