（运筹学与控制论专业论文）图的d1全标号问题.pdf

图的( d ，1 ) 一全标号问题 摘要 本学位论文研究的( d ，1 ) 全标号源于以无线电为背景的距离2 标号i 口- j 题 用g = ( v e ) 表示一个顶点集为矿边集为e 的有限简单无向图g 的k 一( d ，1 ) - 全标号定义为从集合v ( c ) ue ( g ) 至t j ( 0 ，1 ，) 的映射使得相邻的顶点标号 不同，相邻的边标号不同，相关联的点和边的值差至少为d g 的( d ，1 ) 全标号 数碍( g ) 是g 的所有的一( d ，1 ) 一全标号中最小的免值。 2 0 0 2 年，h a v e t ；g l y u t l 】最先引进- r ( a ，1 ) 一全标号这一概念，并猜想：( g ) z x ( g ) + 2 d 一1 ，其中( g ) 表示g 的最大度 本学位论文主要是围绕这个猜想展开研究 在第一章中，我们给出了一些基本概念以及图的( d ，1 ) 全标号问题的研究背 景和现状，并介绍了本学位论文的主要结果 在第二章中，我们证明了最大度至少为4 的树满足某些条件时它的( 2 ，1 ) 全标 号数等于最大度 在第三章中，我们完全刻画了路与路的联图的( 2 ，1 ) 全标号数，同时也 刻画了除去亿= m + 1 ，m 1 4 且m 三2 ，4 ( m o d1 2 ) 这种情况的圈与圈的联 图vg 的( 2 ，1 ) 全标号数 在第四章中，我们考虑了广义p e r t e r s o n 图的( d ，1 ) 全标号数，其中d 3 ；并求 出了p e r t e r s o n 图的( 2 ，1 ) 全标号数 关键词：( d ，1 ) - 全标号；l ( a ，1 ) - 标号；l ( p ，g ) 标号；全标号数；最大度 t h ep r o b l e m o f ( d ，1 ) - t o t a ll a b e l i n g i ng r a p h s a b s t r a c t i nt h i st h e s i s ，w es t u d yt h e ( d ，1 ) 一t o t a ll a b e l i n go fg r a p h s ，w h i c hi sas p e c i a lo f d i s t a n c et w ol a b e l i n go fg r a p h sm o t i v a t e db yt h ef r e q u e n c yc h a n n e la s s i g n m e n tp r o b l e m l e tg = ( k e ) b eaf i n i t e ，s i m p l ea n du n d i r e c t e dg r a p hw i t ht h es e to fv e r t i c e s va n dt h es e to fe d g e se a ( d ，1 ) 一t o t a ll a b e l i n go fag r a p hgi sam a p p i n gff r o m v ( c ) ue ( g ) t ot h el a b e ls e t o ，1 ，尼) s u c ht h a ta n y t w oa d j a c e n tv e r t i c e sh a v e d i f f e r e n tl a b e l s ，a n yt w oa d j a c e n te d g e sh a v ed i f f e r e n tl a b e l s ，a n da n yi n c i d e n tv e r t e x a n de d g eh a v et h el a b e ld i f f e r e n c ea tl e a s td t h e ( d ，1 ) 一t o t a ln u m b e r ( g ) o fag r a p h gi st h el e a s tks u c ht h a tgh a sa 七一( d ，1 ) 一t o t a ll a b e l i n g i n2 0 0 2 ，h a v e ta n dy u 1 1i n v e s t i g a t e dt h e ( d ，1 ) t o t a ll a b e l i n go fg r a p h sa n dc o n j e c t u r e dt h a t ：( g ) ( g ) 4 - 2 d 一1 ，w h e r ea ( g ) d e n o t e st h em a x i m u md e g r e eo f g t h i st h e s i si sb a s e do nt h i sc o n j e c t u r e i nc h a p t e r1 ，w ec o l l e c ts o m eb a s i cn o t i o n su s e di nt h et h e s i sa n dg i v eac h i e f s u r v e yo nt h i sd i r e c t i o n m a i nr e s u l t si nt h et h e s i sa l es t a t e d i nc h a p t e r2 ，w es t u d yt h e ( 2 ，1 ) 一t o t a ln u m b e ro ft r e e sw i t hs p a r s ev e r t i c e so fm a x - i m u md e g r e ei se q u a lt oi t sm a x i m u md e g r e e i nc h a p t e r3 ，w ec h a r a c t e r i z ec o m p l e t e l yt h e ( 2 ，1 ) 一t o t a ln u m b e ro ft h ej o i no ft w o p a t h s a l s ow ed e t e r m i n et h e ( 2 ，1 ) t o t a ln u m b e ro ft h ej o i no ft w oc y c l e sg kvg w i t ha ne x c e p t i o nt h a tn = m + 1 ，m 1 4a n dm 兰2 ，4 ( m o d1 2 ) i nc h a p t e r4 ，w es t u d yt h e ( d ，1 ) 一t o t a ln u m b e ro fg e n e r a l i z e dp e t e r s o ng r a p h ，w h e r e d 3 ；w ea l s og i v et h e ( 2 ，1 ) 一t o t a ln u m b e ro fp e t e r s o ng r a p h i k e yw o r d s ： ( d ，1 ) 一t o t a ll a b e l i n g ；l ( d ，1 ) 一l a b e l i n g ；l ( p ，g ) 一l a b e l i n g ；t o t a lh u m - b e r ；m a x i m u md e g r e e i v 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他 机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 己在论文中作了明确的声明并表示了谢意。 研究生签名：彭彳争 日期：力哗f 夕 学位论文使用授权声明 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件和电子文档，允许论文被查阅和借阅，可以采用影 印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不同方 式在不同媒体上发表、传播论文的全部或部分内容。保密的学位论文在解密后 遵守此协议。 研究牛签名煮街 翩虢稚气吼 吖- 1 1 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理 条例。我的学位论文中凡引用他人已经发表或未发表的成 果、数据、观点等，均己明确注明并详细列出有关文献的名 称、作者、年份、刊物名称和出版文献的出版机构、出版地和 版次等内容。论文中未注明的内容为本人的研究成果。 如有违反，本人接受处罚并承担一切责任。 承诺人( 研究生) ：盏移 指导引矾御屯 1 1 基本概念 1绪论 在本节中，我们定义一些本学位论文中要用到的图论的基本术语与符号 个有序对g = ( ve ) 称为一个无向图，其中y 是一个有限集合，e 是y 中的不 同元素的无序对的集合y 中的元素叫做g 的顶点，e 中的元素叫做g 的边通 常用y ( g ) ，e ( g ) 分别表示g 的顶点集合和边集合没有重边和环的图l 做简单 图除非特别指出，本文研究的图均指有限简单无向图通常称含有佗个顶点的 图为霸点图对于g 的顶点毪和掣，若边e = 删e ( g ) ，则称u 和v 相邻，越和u 互为 邻点；称u 和u 是e 的端点，u 和u 分别与e 关联在g 中与顶点乱相邻的顶点的全体叫 做u 的邻域，记作g ( u ) ；并把g m = g ( u ) u u ) 称作点u 的闭邻域称i g ( u ) i 为 项点u 的度数，记作始( u ) 称度数为七的顶点为k 度点g 中顶点的度中最大者和 最小者分别称为g 的最大度和最小度，分别记作( g ) 和6 ( g ) 每对不同的顶点都 相邻的简单图叫做完全图，仃个顶点的完全图记为在不产生混淆的情况下，我 们把( g ) ，g ( v ) ，如( v ) ，分别简记为，拟，) ，d ( v ) 对图g = ( v e ) 和图h = ( v ，e ，) 若有y 7sy ，e 7 e ，则称图日是图g 的 一个子图对于y ，我们把g 5 b 属于y 的顶点以及与中的点关联的边 都删除所得到的图记作e v 或g 一对于gy ，我们把由y 作为顶点集， e = e l e = 伽e ，u ，u v ) 作为边集的图叫做g 中由顶点子集y 导出的子图， 记作g 图g 的一条途径是一个有限非空的点边交替序列w = v l e l v l e 2 e 蠢仉，使得 对1 1 ) 的复杂 性依然是开放的，很多学者在这方面做了非常大的努力，见文献【1 5 】 关于平面图的l ( 2 ，1 ) 标号问题，v a nd e nh e u v e l 和m c g u i n n e s 1 6 1 已证明猜 想1 1 对a ( g ) 7 的平面图g 成立w a n g 和i l i h t l 0 1 根据平面图g 的围长9 ( g ) 得到 了下面结论： 若g ( g ) 7 ，则入，k ( v ) ( 2 k 一1 ) a ( g ) + 4 h + 4 k 一4 ； 若g ( c ) 6 ，则入h ，k ( v ) ( 2 k 一1 ) ( g ) + 6 h + 1 2 k 一9 ； 若g ( c ) 5 ，则入_ l ，七( g ) ( 2 k t ) x ( v ) + 6 h + 2 4 k 一1 5 w h i t t l e s e y , g e o r g e s 和m a u r o 在【1 7 】中研究了关联图的l ( 2 ，1 ) - 标号问题一个 图g 的关联图是把g 的每条边用长为2 的路替换后得到的g 的关联图的l ( 2 ，1 ) 标 号问题等价与对v ( e ) ue ( g ) 的每个元素分配一个整数使得相邻的顶点有 不同的标号，相邻的边有不同的标号，相关联的点和边标号差至少为2 这个 标号就叫做( 2 ，1 ) 一全标号2 0 0 2 年，h a v e t 和y u t l l 将其推广为( 吐1 ) 一全标号这一形 式设d 1 为一个整数图g 的七一( d ，1 ) 一全标号是一个从v ( g ) ue ( g ) 到标号集 合 o ，1 ，七) 的映射，使得 ( 1 ) 当z 和y 是相邻的顶点时，p ) ，( 可) ； ( 2 ) 当e 和e 是相邻的边时，( e ) ，( e ，) ( 3 ) 当z 和e 是相关联的点和边时，i ，( z ) 一，( e ) i d g 的( d ，1 ) 一全标号数定义为g 的所有的艮一( d ，1 ) 一全标号中的最小的七值，记 做碍( g ) 当d = l 时，( 1 ，1 ) - 全标号也就是著名的图的全染色问题在【8 ，1 8 ，1 9 c o 已经广泛地研究了这个问题 h a v e t 和y u f l l 深入研究了碍( g ) 的上界，也就是关于图g 最大度( g ) 的函数， 证明- r 碍( v ) 2 a ( g ) + d 一1 但是对于最大度较大的图，这个上界不是紧的 于是他们给出了下面的猜想： 3 1 绪论 猜想1 2a l ( a ) a ( g ) + 2 d 1 如果猜想1 2 成立，我们就有a 手( g ) m i n z x ( g ) + 2 d 一1 ，2 z x ( g ) + d 一1 ) 当d = 1 时，这个猜想也就是全染色猜想：) ( ”( g ) a ( g ) + 2 ，其中x ”( g ) 表示g 的 全色数 在文献【2 0 】中，作者证明了下面的结论对任意图g 有，( 1 ) 碍( g ) 2 a ( g ) + d 一1 ；( 2 ) 入：( g ) 2 a ( g ) 一2 1 0 9 ( a ( g ) + 2 ) + 2l o g ( 1 6 d 一8 ) ；( 3 ) 入；( g ) 2 ( g ) ； ( 4 ) 若a ( a ) 5 且为奇数，则碍( g ) 2 a ( g ) 一1 人们已经研究了很多特殊图 类的( d 1 ) 一全标号问题，例如，完全图【2 0 】，图的积图 2 1 1 ，平面1 虱 2 2 1 ，完全二部 图 2 3 1 ，给定最大平均度的图【2 4 】，外平面图【2 5 】，树 2 6 1 ，等等文献【2 7 】中给出了 一个图的全染色的更一般的推广 b a z z a r o 和m o n t a s s i e r l 2 2 1 证明了下面的结果： 定理1 1 若g 满足以下关于围长夕( g ) 和最大度( g ) 的条件之一，则碍( g ) a ( g ) + d 一2 ： ( g ) 2 d + 1 且9 ( c ) 1 1 ； a ( g ) 2 d + 2 _ l i g ( g ) 6 ； ( g ) 2 d + 3 a g ( g ) 5 ； a ( c ) 8 d + 2 考n 图n ( 2 ，1 ) 全标号数与最大平均度的关系，m o n t a s s i e r 雨 r a s p a u d 2 4 1 得到 了下面的结果： 定理1 2 若g 的最大平均度m a d ( g ) 满足以下条件之一，则a 手( g ) a ( g ) + d - 2 ： ( g ) 2 d + 1 a m a d ( g ) ； a ( c ) 2 d + 2 a m a d ( g ) 3 ； ( g ) 2 d + 3 _ 目m a d ( g ) 警， 其中，m a d ( g ) = m a x 2 1 e ( h ) i i v ( h ) i ，h g ) 最近，w a n g 刁g l c h e n 给出t a ( t ) = 3 的树的( 2 ，1 ) 一全标号数的一个完全刻画， 4 1 绪论 并且还给出了外平面图的一些结果 定理1 3f 2 6 1 若丁是( t ) = 3 的树，则碍( t ) = 4 当且仅当丁是好树 定理1 4 瞄】设g 是外平面图则 ( 1 ) 若a ( c ) 2 ，则碍( g ) 4 ； ( 2 ) 若( g ) = 3 且g 是2 - 连通的，则遐( g ) 5 ； ( 3 ) 若( g ) = 4 ，g 9 2 一连通的且不含有相交三角形，则a ( g ) 6 ； ( 4 ) 若( g ) 5 ，则入手( g ) a ( g ) + 2 1 3 本论文的主要结果 本学位论文主要是围绕猜想1 2 展开研究的，得到的主要结果如下： ( 1 ) 证明了：若t 是一个a ( t ) 4 的树，且不含相邻的最大度点，或不含距离 为2 的最大度点，贝j j a t ( t ) = ( t ) ( 2 ) 确定了路与路联图的( 2 ，1 ) 全标号数；确定了圈与圈联图( 除一些特殊情 况外) 的( 2 ，1 ) 一全标号数 ( 3 ) 对d 3 ，确定了广义p e r t e r s o n 虱的( d ，1 ) 全标号数；同时也给出y p e r t e r s o n 图 的( 2 ，1 ) 全标号数 5 2 树的( 2 ，1 ) 一全标号 在本章中，我们把( g ) 简记为令t 是3 的树我们用i 丁l 表示t 的顶点 数若顶点钉的度d ( t ，) 为，则称可为大点；若d ( v ) z ( q ) 的路p ，因此2 d i a m ( t j ，4 ( s 玑) ) 3 如果d i a m ( t u 4 ( s 玑) ) = 2 ，由断言2 知，s 是一个4 柄，这就得到y ( c 4 ) 假 设d i a m ( t u 4 ( s u 4 ) ) = 3 令8 1 ，8 k 表示8 的不同于弘的邻点，l k 3 由于t 不 含( c 1 ) ，易得每个8 t 都是4 一柄这也就是说2 d ( s ) 3 ，即1 k 2 如果k = 1 ， 则可得( c 2 ) 如果k = 2 ，则可得( c 5 ) 引理2 5 的证明完毕 用相同的方法，我们可以证明下面的引理 引理2 6 令t 是5 的树且不是星如果1 隹d ( t ) ，则丁包含下面子图形之一： ( b1 ) 一个叶子与一个小点相邻 ( b 2 ) 一个小点 与d ( v ) 一1 个大柄相邻 定理2 1 令丁是4 且l 隹d ( 丁) 的树，则丁是第一类的 i y n ：我们对l t i 进行归纳证明如果i t l = 5 ，这个定理很容易证明令丁是i t l 6 ，a 4 且1 譬d ( t ) 的树如果t 是星，很容易构造丁的一个用b = o ，1 ，+ 1 ) 标号的( 2 ，1 ) 一全标号因此。假设t 不是星 如果t 包含一个叶子刀与一个小点心相邻，则由归纳假设t 一可有一个用召= o ，1 ，+ 1 ) 标号的( 2 ，1 ) 一全标号i ，( 或者由于对于每个树t 都有碍( r ) ( 丁) + 2 ) 由于d ( 让) 一l ，对边7 3 7 2 最多有一2 + 3 = + 1 个禁用标号且 q 2 树的( 2 ，j ) 令坏号 对点u 最多有4 个禁用标号由于l b i = + 2 ，我们可以把，扩展n v u 并可扩展到u 因此，假设叶子不能跟小点相邻 首先，假设5 由引理2 6 ，t 包含子情形( b 2 ) ，也就是说，一个小 a v 和d ( v ) 一1 个大柄x l ，x 2 ，x d ( ) 一l 和一个另外的点秒相邻令 d ( v ) - i r = t u ( l ( z ) u ( z ) ) i = 1 由归纳假设，f 有一个在标号集召= o ，1 ，+ 1 ) 上的( 2 ，1 ) 全标号，如 果，( u ) 譬( o ，+ 1 ) ，则由引理2 3 知厂能够扩展i i t j i t l 拘( 2 ，1 ) 全标号假设厂( ) o ，+ 1 用标号集召 o ，+ 1 ，( 秒) ，f ( v u ) 一1 ，( ) ，f ( v y ) + 1 】中的标号 对 重新标号由于i 召 ，我们把z 重新标号成1 由引理2 4 ，能扩展到t ( c 4 ) 令r = t 一 让1 ，让2 卜一l ( u 1 ) - l ( u ：) 由对称性，我们假设f ( v ) o ，1 ，2 ) 如果f ( v ) = 0 ，证明同情形( 3 2 ) 假设f ( v ) = 1 可得f ( v u ) 3 ，4 ，5 ) - 如果，( t ，u ) 4 ，5 ) ，我们把让重新标号 成2 如果， 钍) = 3 ，则f ( v v l ) 4 ，5 ) 首先交换u u 和v v l 的标号，然后把u 重新标 号为2 ，u 重新标号为o 由引理2 3 和2 4 ，能扩展到整个t 上 假设f ( v ) = 2 可知，( 口让) o ，4 ，5 ) 如果f ( v u ) = 0 ，我们把珏重新标号成3 如果f ( v u ) 4 ，5 ) ，我们把札重新标号成1 由引理2 4 ，能扩展到t ( c 5 ) 证明分成下面两种子情形： ( 5 1 ) d ( z ) = 4 令t 7 = t - u ，口，乱l ， t 2 ，t ，1 ，耽) 一( 乱1 ) 一己( 乱2 ) 一l ( u 1 ) 一l ( 忱) 由引理2 1 ( 3 ) ，f ( z ) o ，5 ) ，不失一般性令f ( z ) = 0 因此，f ( z w ) 2 ，3 ，4 ，5 ) 可 以构造下面的标号： 如果f ( z w ) = 2 ，我们分别用4 ，0 ，1 ，3 ，3 建 1 w ，叫钆，w v ，u ，u 重新标号 11 2 树的( 2 ，1 ) 一伞标号 如果( z w ) = 3 ，我们分别用l ，4 ，5 ，2 ，2 e w ，伽钆，w 1 ) ，u ，u 重新标号 如果( z w ) = 4 ，我们分别用2 ，0 ，5 ，3 ，1 对伽，w i z ，w u ，u ，u 重新标号 如果( z w ) = 5 ，我们分别用2 ，0 ，4 ，3 ，l 对叫，w a ，w v ，u ，u 重新标号 ( 5 2 ) d ( z ) 3 令t 7 = t 一 u l ，u 2 ) 一l ( u t ) 一l ( 乱2 ) + w y ，其中可譬y ( t ) 是 一个新的顶点很容易得至! l j l t l 上的( 2 ，1 ) - 全标号由 于w 在t 7 中的度为4 ，由引理2 1 ( 3 ) 得f ( w ) _ o ，5 ) ，不失一般性令厂( 叫) = 0 因此， ，( 棚让) 2 ，3 ，4 ，5 ) 把可移除，可以通过下面方法扩展n t ：如果( w u ) = 2 ，我 们把u 重新标号成4 ；如果，( 叫乱) 3 ，4 ，5 ) ，我们把乱重新标号成1 证毕 2 2 满足2 彰d 的树 回顾一下，2gd 的含义是丁中不含两个距离为2 的最大度点如果v 只与两 个度大于l 的顶点相邻，则称顶点v 为弱柄弱大柄是指度为的弱柄 引理2 7 令t 是4 的树且2 岳d a ( t ) ，如果t 不是广义星，则t 包含下面子 图形之一： ( d 1 ) 一个叶子与一个小点相邻 ( d 2 ) 一个2 点与一个大柄相邻 ( d 3 ) 一个大柄与一个弱大柄相邻 证明：如果t 含( d 1 ) ，证明完毕假设丁不含( d 1 ) 则每个叶子都跟最大度点相邻 令p = x o x l z 2 z m 表示t 中的最长路则z o ，x m 是叶子并且z l ，x m - 1 是大柄由 于t 不是广义星且2gd ( 丁) ，很容易得到m 5 如果d ( x 2 ) = 2 ，则t 包含( d 2 ) 假设d ( x 2 ) 3 令y 是z 2 的不同于z 1 和z 3 的邻点因为2gd a ( t ) ，故d ( y ) 一1 假设d ( y ) 2 令z x 2 是可的邻点因为g 不含( d 1 ) ，d ( z ) 2 ，因此有一 个顶点z 7 夕与z 相邻然而，q = z t z y x 2 x 3 z m 是丁中的路且z ( q ) 粤( p ) ，矛盾 1 2 2 树的( 2 ，1 ) 一伞标号 因此，d ( y ) = 1 ，也就是说，z 2 的除去z 1 和z 3 所有邻点都是叶子由于g 不包含( d 1 ) ， 故z 2 是一个弱大柄，因此得到( d 3 ) 证毕 定理2 2 令t 是a 4 的树且2 d a ( t ) ，则t 是第一类的 证明：我们对i 丁i 进行归纳假设如果i t i = 5 这个定理显然成立令t 是i t i 6 的 树，4 j | 2zd a ( t ) 如果丁是一个广义星，很容易证明a ；( t ) = + 1 因此， 假设丁不是广义星由引理2 7 ，t 含有( d 1 ) ( d 3 ) 中的情形之一如果t 包含( d 1 ) ，这 个证明同定理2 1 中对应的情况一样因此，我们只需考虑下面两种情况： 2 ) 假设g 包含一个2 一点z 2 与一个大柄z 1 和另一个顶点x 3 相邻由归纳假设， t z l l ( x 1 ) 有一个在标号集b = o ，1 ，+ 1 】上的( + 1 ) 一( 2 ，1 ) 一全标号， 如果f ( x 2 ) o ，a + 1 ) ，不失一般性令，( z 2 ) = 0 ，我们把z l 标号为+ 1 ， 用召 o ，1 ，+ 1 ，( z 2 2 3 ) ) 中的标号对z l z 2 进行标号由于l 召i = a + 2 6 ，故 对z l z 2 的标号是可行的 如果f ( x 2 ) g o ，+ 1 ) ，我们用召 ，( z 2 ) ，f ( x 2 ) - i ，f ( x 2 ) + l ，f ( x 2 x 3 ) 中的标 号对边x l x 2 标号；用 o ，+ 1 ) ，( z 2 ) ，f ( x l x 2 ) - i ，( z l z 2 ) ，f ( x l x 2 ) + l 中的标号 对z 1 进行标号由于i 召l = a + 2 6 且最多只有f ( x l x 2 ) - i ，f ( x l x 2 ) ，f ( x l x 2 ) + l r o 的一个可能是o 或+ 1 ，因此，对z l z 2 和z 1 的标号是可行的 ( d 3 ) 假设g 包含一个大柄z 1 与一个弱大柄z 2 相邻令z 3 z 1 是z 2 不是叶子的 邻点因为g 不是广义星，这样的z 3 一定存在由归纳假设，t l ( x 1 ) 有一个在标 号集8 = o ，1 ，+ 1 ) 上的( + 1 ) 全标号， 由引理2 1 ( 3 ) ，f ( x 2 ) o ，a + 1 - ，不失一般性令， 2 ) = 0 我们把x l 重新标 号为+ 1 如果f ( z l 现) 譬 ，+ 1 ，易得，能够扩展到整棵树t 上否则，因 为d ( x 2 ) = 4 ，存在一个叶子! l ( x 2 ) j | f ( y x 2 ) 譬 ，+ 1 ) 我们交换 z l z 2 和y x 2 的标号，则用合适的标号对y 重新标号由引理2 4 ，能够扩展到整棵 树t 上证毕 令y v 】= n ( v ) u 口) 设3 m 表示与 的距离至少为3 的顶点的集合 下面的这个使得a ( t ) = + 1 的充分条件最近在文献 2 8 1 中给出了，也就是 我们定理2 2 中a 8 时的情形 1 3 2 树的( 2 ，1 ) 一伞标号 定理2 3 令t 是一个树，如果对任意的顶点u y ( t ) ，n 3 m 最多包含一6 个大 点，m 最多包含2 个大点，i ) l j a ( t ) = a + 1 事实上，如果p 是满足8 和2 簪d a ( t + ) 的树，则丁+ 的关联图t 也是一 - q a ( t ) = a ( t ) 的树很容易检验，n 3 秒】最多包含丁中的2 ( ( t ) 一6 ) 个大点， m 也是这样因此，由定理2 3 得，入；+ ( t ) = a ( 丁) = a ( t ) + 1 = a ( t + ) + 1 2 3 结论 定理2 1 和定理2 3 断言，当丁是4 且1 或2gd ( t ) 的树时，a t ( t ) = a 十1 这个结果是关于d a ( t ) 分类的最好的可能我们可以给出下面的结果： 定理2 4 对任意整数七，m 3 ，蒯e a ( t ) = m 且尼隹d ( ) 的树，使得碍( ) = m + 2 证明：对任意m 3 ，令表示执行下面两步后得到的图： ( 1 ) 取一个由1 个m 一点x 和m 个1 一点可1 ，沈，组成的星k t m ； ( 2 ) 对i = l ，2 ，m ，给每个y i 粘m 一1 个叶子 显然，是一棵= m 的树且x ，y 1 ，都是的大点很容易得n 1 ，2 d z - ( t m ) ，且对任意的忌3 ，k 簪d a ( t m ) 由引理2 2 得，碍( ) = a + 2 证毕 在结束本节前，我们提出下面的问题： 问题：刻画( t ) 4 的树t ，使得入手( 丁) = + i 或a t ( t ) = a + 2 1 4 3 联图8 9 ( 2 ，1 ) 一全标号数 两个图g 和日的联图gvh 是g 中的每个点和日中的每个点相连接得到的图 假设= 锃l 笛2 锰1 和g = u 1 u 2 l 是两个点不交的圈且n ，仇3 则c vc k 定义如下： y ( vg ) = y ( ) uy ( g ) ， e ( vg ) = e ( ) ue ( g ) u 【哟：i = 1 ，2 ，m ；j = l ，2 ，札) 若= u l u 2 t m 和r = v l v 2 是两条不相交的路且几，m 1 ，类似的 我们有： y ( 岛vr ) = y ( 焉) uy ( r ) ， e ( 岛vr ) = e ( 岛) ue ( r ) u u i v j ：i = 1 ，2 ，m ；j = 1 ，2 ，乳) 在本章中，我们研究了路与路的联图和圈与圈的联图的( 2 ，1 ) - 全标号问题 3 1 圈与圈的联图 引理3 1 ( 2 0 】) 令n 3 是任意的整数则 a c 玫，= ：三：喜二乒6 8 或死是奇数； 令g 表示由图g 的最大度点导出的子图，简记= ( g ) w a n g 和c h e n t 2 5 1 证 明了下面的结果： 引理3 2 若a ( g a ) a 一1 ，贝i j a t ( g ) a + 2 引理3 3 若g 不是二部图，则碍( g ) + 2 证明：用反证法证明，假设碍( g ) = a + i 令，表示g 在标号集 o ，1 ，+ 1 ) 上 的一个( + 1 ) 一( 2 ，1 ) - 全标号由引理2 1 ( 3 ) ，对g 的每个最大度点u 都有，( 钞) = 1 5 3 联图的( 2 ，1 ) 全标号数 0 或厂( t ，) = + 1 因此，在g a _ h 有个合适的2 染色，n n g a 是二部图，这与前 提矛盾证毕 给出g 的一个在标号集b = o ，1 ，忌) 上的尼一( 2 ，1 ) 一全标号，令吼和屈分 别表示标号为i 的顶点数和边数更进一步，我们用记号_ z l ，x 2 ，) _ ( b l ，b 2 ，玩) 表示重复用标号序列6 1 ，5 2 ，b t 进行标号的顶点或边x l ，而，易 的序列例如， u 1 ，e l ，v 2 ，e 2 ，v 3 ，e 3 ，v 4 ，e 4 ，v 5 ) _ ( 1 ，2 ，3 ，4 ) 表示子集v l ， u 3 ，u 5 ) 中 的元素标号都是l ， e 1 ，e 3 ) 中的元素标号都是2 ，v 2 ，吼) 中的元素标号都是3 ， e 2 ，e 4 ) 中的元素标号都是4 对一个子集s v ( g ) ue ( g ) 和一个标号i b ， f ( s ) = i 表示s 中所有标号为j 的元素特别的，对每个z 【n ，b ，c ，我们简记 为，( z ) = i 定理3 1 令佗，m 是整数且n m 3 则 入；c vg ，= ：三 霎：茎暑萋兰：三：主三是奇数 证明：令g = vg 由于礼m 3 ，则有= 礼+ 2 在下面的讨论中，u i 的下 标i 取模m ，的下标j 取模n 证明分成以下几种情形： 情形1m 是偶数 子情形1 1 死仇+ 3 由引理2 1 ( 1 ) ，g ( a ) a + i = n + 3 只需给出g 在标号集 o ，1 ，n + 3 ) 上 的一个( n + 3 ) 一( 2 ，1 ) - 全标号，： u l ，1 7 2 2 ，u 2 ，乱2 u 3 ，u r n - 1 u m ，u m ，u 1 ) - ( 0 ，2 ，礼+ 3 ，3 ) ； ，( 口1 ) = f ( v a ) = l ； f ( v 2 ) = 2 ； 当4 jsn m + 2 时，( ) = j 一2 ； 当n m + 3sj isn 时，( ) = j ； f ( v j v d + 1 ) = m + 3 + j ，其中j ；1 ，2 ，3 ； “气 3 3 联图的( 2 ，i ) 伞标号数 当4 歹sn m + l 时，f ( v m + 1 ) = j + 1 ； ，( t k m + 2 t 一m + 3 ) = 0 令n m + 3 j 佗， 若扎是奇数，歹是偶数时，我们令，( + 1 ) = 2 ；j 是奇数时，令，( 哟+ 1 ) = 3 若n 是偶数，j 是偶数时，我们令y ( v m + 1 ) = 3 ；j 是奇数时，令f ( v j v j + 1 ) = 2 对所有的i ，j g i + j 3 ，若i + j + 1 n + 3 ，令y ( u l v j ) = i + 歹+ 1 ；否则， 令f ( u v j ) = p + 3 ，其中z + 歹+ 1 三p ( m o d ( n + 3 ) ) 勘1 我们把一m + l 重新标号为0 ，一m + 2 重新标号为1 ，u 1 口1 重新标号为死+ 3 对t = 2 ，4 ，m 一2 ，把满j 足：f ( u i v j j = n + 2 的边u t 重新标号为1 ，把满 足f ( 札i v j + 1 ) = n + 3 的边讹+ 1 重新标号为0 例如，表3 i 给出了c 8va l 的一个1 4 ( 2 ，1 ) 一全标号 3 1 2 1 3 1 45 3 2 3 2 32 濑 12l236 7 891 0l o1 44567891 01 11 21 3 2 1 44567891 01 11 2lo 3 0567891 0l l1 21 31 44 2 1