（运筹学与控制论专业论文）图的ld1标号.pdf

图的l ( d ，1 ) 标号 摘要 本文所考虑的图都是简单的有限图，给定一个图g ，我们用y ( g ) ，e ( g ) ， n ( g ) 分别表示它的顶点集合，边集合和最人度图g 的一个k - l ( d ，1 ) 一标号 是一个从v ( a ) 到标号集合 o ，l ，尼) 的映射，使得当z 和y 相邻时有 i y ( x ) 一，( ! ，) l d ，当z 和y 距离为2 时有l f ( x ) 一- 厂( 可) l l - g 的l ( d ，1 ) 一标号数 a e ( g ) 定义为g 的所有k - l ( d ，1 ) 一标号中最小的k 值 图的l ( 2 ，1 ) 一标号问题起源于h a l ef 1 】的频道分配问题。这类问题近年来 得到广泛研究1 9 9 2 年，g r i g g s 和y e h1 2 猜想：对于一个( g ) 2 的图g ，有 a 2 ( g ) 2 ( g ) 当前最好的结果是a 2 ( g ) a 2 ( g ) + ( g ) 一2 ，由g o n ；a l v e s f 3 】 给出 本学位论文在前人的工作基础上继续研究网的l ( d ，1 ) 标号问题在第一章 中，我们给出概念以及图的l ( d ，1 ) 一标号问题的研究背景和现状，并且介绍了本学 位论文的主要结果 在本文的第二，三，四，五章中，我们分别考虑了2 - 夕 平面图的l ( 2 ，1 ) 标号， 广义p e t e r s e n 罔，平面格子点图和三角格子点罔的l ( d ，1 ) 标号问题我们的主要 结果如下： ( 1 ) 对于任意的2 - 夕 平面图g ，入2 ( g ) a ( g ) + 1 2 ( 2 ) 对于任意的广义p e t e r s e n p ( n ) ，若d 3 且钆3 ，则扎( p ( n ) ) 3 d + 3 ( 3 ) 确定了平面格子点图和三角格子点图的l ( d ，1 ) 标号数 关键词：l ( d ，1 ) 一标号，2 - 夕f 平面图，广s ( p e t e r s e n ，平面格子点图，三角格子点 i 图，频道设计 l ( d ，1 ) - l a be l l i n go fg r a p h s a b s t r a c t a l lg r a p h sc o n s i d e r e di nt h i sp a p e ra r ef i n i t es i m p l eg r a p h s f o rag r a p hg ，w e d e n o t ei t sv e r t e xs e t ，e d g es e ta n dm a x i m u md e g r e eb yy ( g ) ，e ( g ) a n d ( g ) r e s p e c t i v e l y ak - l ( d ，1 ) - l a b e l l i n go fag r a p hgi saf u n c t i o n ，f r o mi t sv e r t e xs e tv ( c ) t o t h el a b e ls e t o ，1 ，惫) s u c ht h a tl f ( x ) 一，( 可) di f $ a n d 可a r ea d j a c e n t ，a n d l ，( z ) 一，( 拶) l 1i f a n dya r ea td i s t a n c e2 t h el ( d ，1 ) - l a b e l l i n gn u m b e rx d ( g ) o f gi st h es m a l l e s tks u c ht h a tgh a sak - l ( d ，1 ) - l a b e l l i n g t h e l ( 2 ，1 ) 一l a b e l l i n go fag r a p ha r o s ef r o mav a r i a t i o no ft h ef r e q u e n c yc h a n n e l a s s i g n m e n tp r o b l e mi n t r o d u c e db yh a l e 【l 】t h i ss u b j e c th a sb e e ns t u d i e dr a t h e re x t e n s i v e l yi nr e c e n ty e a r s 。i n1 9 9 2 ，g r i g g sa n dy e h1 2 c o n j e c t u r e dt h a ta 2 ( g ) 2 ( g ) f o ra n yg r a p hg w i t h ( g ) 2 ，t h eb e s tk n o w nu p p e rb o u n da 2 ( g ) + a ( g ) 2f o r a 2 ( g ) w a se s t a b l i s h e db yg o n g a l v e s 【3 】 i nt h i st h e s i s ，w ec o n s i d e rt h el ( d ，1 ) - l a b e l l i n gf o rs o m eg r a p h s i nc h a p t e r1 ，w e c 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 fs u r v e yo nt h i sd i r e c t i o n i nc h a p t e r2 ，3 ，4 ，5 ，w es t u d yt h el a b e l i n gp r o b l e mo f2 - o u t e r p l a n a rg r a p h s ，g e n e r a l i z e dp e t e r s e ng r a p h s ，p l a n a rg r i d s ，t r i a n g u l a rg r i d s o u rm a i nr e s u l t si nt h ep r e s e n t p a p e ra r ea sf o l l o w s ： ( 1 ) f o re v e r y2 - o u t e r p l a n a rg r a p hg ，a 2 ( g ) a ( a ) + 1 2 ( 2 ) f o re v e r yg e n e r a l i z e dp e t e r s e ng r a p hp ( g ) ，i fd 3a n d 佗3 ，t h e n 入d ( p ) ) 3 d + 3 ( 3 ) c h a r a c t e r i z et h el ( d ，1 ) 一l a b e l l i n gn u m b e ro fp l a n a rg r i d sa n dt r i a n g u l a rg r i d s i k e yw o r d s ：l ( d ，1 ) - l a b e l l i n g ；2 - o u t e r p l a n a rg r a p h ；g e n e r a l i z e dp e t e r s e ng r a p h ； p l a n a rg n d s ；t r i a n g u l a rg r i d s ；c h a n n e la s s i g n m e n t i v 浙江师范大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机 构已经发表或撰写过的研究成果其他同志对本研究的启发和所做的贡献均已在 论文中作了明确的声明并表示了谢意本人完全意识到本声明的法律结果由本人 承担 名：步匀一 嗽年月二日 学位论文使用授权声明 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关机关或机构送交论文的复印件和电子文档，允许论文被查阅和 借阅，可以采用影印、缩印或扫描等手段保存、汇编学位论文同意浙江师范大 学可以用不同方式在不同媒体上发表、传播论文的全部或部分内容 保密的学位论文在解密后遵守此协议 作者主名：澎身吒师签名：乡功几吼 04 5 多月z 日 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理 条例我的学位论文中凡引用他人已经发表或未发表的成果、 数据、观点等，均已明确注明并详细列出有关文献的名称、作 者、年份、刊物名称和出版文献的出版机构、出版地和版次等 内容论文中未注明的内容为本人的研究成果 如有违反，本人接受处罚并承担一切责任 承诺人( 研究生) ： 指导教师： 劫豸矿 尹伊 1 1 基本概念 1绪论 在本节中，我们定义一些本学位论文中要用到的图论的基本术语与符号一 个有序对g = ( ke ) 称为一个无向图，其巾y 是一个有限集合，e 是y 中的不 同元素的无序对的集合y 中的元素叫做图g 的顶点，e 中的元素叫做图的边 通常用y ( g ) 、e ( g ) 分别表示图g 的顶点集合、边集合没有重边和环的图叫 做简单图除非特别指出，本文研究的图均指有限简单无向图如果能将图g 画 在平面上，使得它的边仅在端点处才可能相交，则称图g 是可平面图图的这种 平而上的画法称为图的平而嵌入，或称为平而图 常用乱，u 表示g 中的点，e 表示g 中的边，表示g 中的面当g 是平面图 时，若边e = 乱口e ( g ) ，则说“，移在g 中相邻，或u 和 互为邻点；这时又说 钍和秽是e 的端点口的全体邻点所形成的集合叫做u 的邻域，记作g ( u ) 设 acy ( g ) ，称n c ( a ) ：= u g ( u ) 为4 的邻域并且把n g 【u 】= b ( u ) u 乱) 记 做点 i t 的闭邻域若点 是边e 的端点，则说u 与e 在g 中栩关联，若顶点v 在面 ，的边界上，则说v 与，在g 中相关联称有一个公共端点的两条边相邻，以及 至少有一条公共边的两个面相邻设口是一个顶点，与v 相关联的边的条数叫做 v 的度数，记作d g ( 秒) g 中的点的最小和最大的度数分别记作6 ( g ) 和a ( g ) ( 或 ) 若d ( v ) = k ( d ( u ) k ，d ( v ) k ) ，则称口为个k 一点( k + 一点，k 一- 点) 我们把 一个与u 相邻的k 点，叫作v 的一个k 邻点用以( 口) 表示v 的k 一邻点的个数 在不产生混淆的情况下，我们把l v ( g ) i ，i e ( g ) i ，g ( u ) ，g 【缸】，d g ( u ) ，( g ) ，6 ( g ) 分别简记为i y i ，l e l ，l n ( u ) l ，l n u l ，d ) ，a ，j 对于图g = ( ke ) 和图h = ( v 7 ，e ，) ，若有y y ，e 7 e ，则称图日是图 g 的个子图对于y 互y ( g ) ，我们把图g 中属于y 的顶点以及与y 7 中的点 关联的边都删除所得到的图记为a v 7 或g 一对于u ，口y ( g ) ，u 1 ) 譬e ( g ) ， 我们把图g 中连接顶点乱，u 所得到的图记为g + 钍 ) 对于y y ( g ) ，我们 1 1 绪论 把由v 作为顶点集，e = e i e = 乱口e ( g ) ，u ，u v ) 作为边集的图叫做g 巾 由顶点子集y 导出的子图，记为g y 】设g l ( ，e 1 ) ，g 2 ( k ，易) 是两个图，称图 g = ( uk ，e 1u 岛) 为图g l 和图g 2 的并，记为gu 日对于e e ( g ) ，若删 去边e ，并令它的两个端点重合，则称边e 被收缩，记收缩边e 后得到的简单图为 g e 图g 的一条途径是一个有限非空的点边交替序列w = r o e l u l e 2 e k v 七，使 得对1 七) ，计算了路和 圈的跨度 w h i t t l e s e y ，g e o r g e s 和m a u r o1 1 9 】研究了平面格子图g n 。m 的l ( 2 ，1 ) 一标号问题， 得到： 定理1 2 入2 ( g m ) = 5 若n = 2 ，m 3 ；x 2 ( g n ，m ) = 6 若钾，m 3 s c h w a r z 和t r o x e l l 2 0 1 研究了圈和圈的笛卡尔积的l ( 2 ，1 ) 标号问题f e r t i n 和 r a s p a u d 2 h 讨论了扎一维格子图的l ( p ，口) 一标号问题j h a 【2 2 】讨论了路和圈，圈和圈 的笛卡尔积的l ( 2 ，1 ) 标号问题，给出了入2 ( 口r ) 和入2 ( 口g ) k l a v s ：a r 2 3 】等 和k u o 2 4 】等学者也独立解决了圈和圈的笛卡尔积的l ( 2 ，1 ) 标号问题，得到结 论： 定理1 3a 2 ( 口g ) - - 4 或5 或6 g e o r g e s 和m a u r o 2 5 , 2 6 研究了完全图纸和的笛卡尔积的l ( 2 ，1 ) 一标号 问题，并且给出了完全图的笛卡尔积的l ( 2 ，1 ) 一标号数： 定理1 4 对完全图纸和，若2 礼m ，则有： ( 1 ) ：入 ，七( 口) = ( m 一1 ) + 一1 ) 尼，当2 n ( 2 ) ：入h ，南( 口) = ( m n 一1 ) 而，当2 n 4 1 绪论 ( 3 ) ：a ，( 砥口) = 一1 ) + ( 2 n 一1 ) 露，当i h 礼一i ( 4 ) ：a ，( k i n 口) = ( 7 1 2 一1 ) 危，当鲁n 一1 对于任意一棵树t ，g r i g g s 和y e h 2 】证明了a 2 ( t ) 不是a ( c ) + l 就是 a ( o ) + 2 ，并胃猜想识别这两种类型是n p h a r d 的c h a n g 和k u o 在 1 7 】中否定 了这一猜想，给出了一个基于动态规划的多项式算法但是，还没有人能够完全刻 画树的l ( 2 ，1 ) 一标号w a n g 【刎给出了入2 ( t ) = ( t ) + 1 的一个充分条件关于树 的z ( h ，后) 标号问题( 后 1 ) 的复杂性是开放的，很多学者在这方面做了非常大的 努力 关于平面图的l ( 2 ，1 ) 标号问题，v a nd e nh e u v e l 和m c g u i n n e r1 2 8 已经证明 猜想1 1 对于27 的平面图成立w a n g 和l i h 【2 9 】根据平面图g 的围长g ( c ) 得 到一下绐论： 定理1 5 ：对于平面图g ，有： ( 1 ) ：若g ( g ) 27 ，则a h ，k ( c ) ( 2 k 1 ) ( g ) + 4 h + 4 k 一4 ( 2 ) ：若g ( c ) 26 ，则a h ，七( g ) ( 2 k 一1 ) z x ( c ) + 6 h + 1 2 k 一9 ( 3 ) ：若9 ( g ) 25 ，则a h ，( g ) ( 2 k 1 ) ( g ) + 6 h + 2 4 k 一1 5 g e o r g e s 和m a u r o 3 0 l i 泛研究了广义p e t e r s e n 的z ( 2 ，1 ) 标号问题，得到以下 结论：对每一个广义p e t e r s e n p ( n ) ，a 2 ( p ( n ) ) 9 ；且a 2 ( 尸( 扎) ) = 9 当且仅当 p m ) 同构于p e t e r s e n 图作为广义p e t e r s e n p ( n ) 的z ( 2 ，1 ) 一标号问题的推广，马 巧灵等人在【3 1 】中证明了：对d 3 ，广义p e t e r s e n e ( n ) 有扎( p ( n ) ) 4 d 1 3 本文的主要研究结果 本学位论文主要围绕g r i g g s 和y e h 的思想，对一些图类的l ( 2 ，1 ) 一标号和 l ( d ，1 ) 标号问题做了研究 在第二章中，我们考虑一般的2 - 夕f 、平面图的l ( 2 ，1 ) 标号问题，得到以下结 果：对于任意的2 - 夕 平面图g ，入2 ( g ) x ( a ) + 1 2 在第三章中，考虑p e t e r s e n i 圉l ( d ，1 ) 标号问题，得到结果：对广义p e t e r s e n e ( n ) 有a d ( p ( n ) ) 3 d + 3 s 1 绪论 在第四章中，我们考虑一般的平而格子点图g n 对一般的平而格子点图 g n ，m 的l ( d ，1 ) 一标号进行了刻画 在第五章中，我们刻画了一般的三角格子点图g n ，m 的l ( d ，1 ) 标号 6 2 2 一外平面图的l ( 2 ，1 ) 一标号 本章主要考虑2 - 夕 、平面图的l ( 2 ，1 ) 一标号问题一个平面图g 称为2 夕f 、平面 图，如果它能嵌入平面使得所有顶点出现在至多两个面 和，2 的边界上记 c ( g ) = ，厶) ，g , 2 _ 2g 的外面集类似地，我们能定义充夕 平面图，k 1 当k = 1 时，g 是通常所说的外平面图 2 1 结构性质 下面引理2 1 2 3 是熟知的结论： 引理2 1 每个阶至少为2 的外平面图包含至少两个度不超过2 的顶点 引理2 2 设g 是一个2 连通的外平面图。则下列断言成立： ( 1 ) 每一个顶点相邻于至多两个2 点 ( 2 ) 对任何两个2 一点心和v ，g ( 牡) g ( u ) 引理2 3 设g 是一个2 连通的外平面图如果g 恰恰包含两个2 点，那么这两 个2 点在g 巾是不能相邻的 下面引理2 4 被隐含在文献 3 2 1 中： 引理2 4 3 2 1 设g 是一个2 连通的外平面图，且t v ( o ) 是一个任意顶点那么， 存在两个棉邻的顶点z ，y v ( a ) t ) 使得d g ( z ) = 2 ，d o ( y ) 4 进一步，我们有一个更强的结果： 引理2 5 设g 是一个阶数至少为4 的2 连通外平面图设s t e ( g ) 是一条位 于外面边界的边那么，存在两个相邻的顶点z ，y v ( a ) s ，) 使得d a ( x ) = 2 ， d g ( y ) 4 7 2 2 - 夕p 平面图的l ( 2 ，1 ) 一棰g - 证明：当l g l 5 时，容易验证结论成立设g 是一个阶数至少为6 的2 一连通 外平面图采用反证法，假设引理结论不成立，即没有这样的顶点z 和y 存 在设秽s ，t 是g 的一个任意2 点，u 1 和v 2 是它的两个邻点由反证法假 设，d g ( 钉1 ) 5 ，d g ( 2 ) 5 如果7 3 1 ) 26y ( g ) ，我们从g 中移去点秽如果 u ，) 2 隹y ( g ) ，我们从g 中移去点v 后再加一条边v l v 2 对v ( c ) s ，t ) 中的所 有2 一点v 都做这样处理后，记最后得到的图为日显然日仍然是一个2 - 连通的 外平面图设26v ( h ) _ 【s ，t ) 是一个任意顶点，那么z6v ( g ) s ，) 满足 d g ( 名) 3 由上面构造方法，每移去一个与z 相邻的2 点，z 的度至多减少1 由引 理2 ( 1 ) ，z 在g 中至多邻两个2 点，因此z 的度至多总共减2 故当如( 名) 5 时， 我们有d j 了( z ) d c ( 名) 一2 3 如果3 d cz ) 4 ，由反证法假设，2 不相邻任 何2 点，因此它的度不发生变化，即妇( z ) = d cz ) 3 这证明了，日中至多有8 和t 是2 点，矛盾于引理3 证毕 引理2 6 一个2 _ 夕 平而图的子图是2 - 夕f 、平而图 证明：令g 为一个2 外平面图，日为图g 的真子图通过册恺；图g 的一个平面 嵌入的某些点和边，我们可以得到图日的平面嵌入对于每一个，6 t ( g ) ，存 在一个y + f ( h ) 使得b ( f ) 一( v ( g ) 一y ( 日) ) b ( f + ) 设s = ，i f t ( g ) ) ， 则i s i 1 。( g ) i = 2 可证日的每一个顶点v 落在s 的某些面上的边界上实 际上，由于v6y ( g ) ，则存在一个面f o6f o m ( g ) 使得口6v ( f o ) 令靠表示s 中 与知对应的面。容易得到v ( 矗) nv ( h ) y ( 靠) 因此，日是一个2 - 外平面图，它 的外面集是s 证毕 设佗3 是整数令表示一个平面图，它由两个点不交的圈c 7 = 2 l x 2 z 。z 1 和c ”= y l y 2 p y l 组成，其巾c 7 被画在c “的内部，然后添加边 x l y l ，秒1 2 2 ，x 2 p 2 ，y 2 x 3 ，z 竹一l 可n l ，一1 z n ，x n 鲰，鼽z 1 显然，是一个4 一正则 的2 - 夕f 、平面图，t ( 魄) = x a x 2 z 礼】， y l p 2 副) 引理2 7 设g 为一个2 外平面图，则 ( i ) 6 ( g ) 4 8 ( 2 ) 6 ( g ) = 4 当且仅当g 竺坛，n 3 i a n ：令t ( g ) = ，五) ，于是v ( a ) = y ( ) uy ( ，2 ) 首先，我们证明断言( 1 ) 若a ( a ) 4 ，则( 1 ) 显然成立假设z x ( c ) 5 若g 包含一个割点v ，不失一般性，假设v y ( ) 令玩，凰，乜( 8 2 ) 为g v 的连通分支对于每一个i = 1 ，2 ，s ，定义导出子图g i = g ( 鼠) u ) 】于是g = g 1ug 2 ug 若尼f ( g 1 ) nf ( g 2 ) ，则6 ( ，2 ) g 1ng 2 由 d g ( ，2 ) 3 可得i y ( g 1 ) ny ( g 2 ) i i y ( 厶) i 3 ，这与y ( g 1 ) ny ( g 2 ) = 钉) 矛 盾因此我们可以假设j 6 2 f ( g 1 ) 这意味着g 1 的每一个顶点都在 的边界上， 换言之，g 1 是顶点数大于2 的外平面图山引理2 1 ，g l 有一个不同于v 的顶点t 使得如。( 仳) 2 显然，d a ( u ) = d a 。( 仳) ，故6 ( g ) 2 ，于是( 1 ) 成立 下面假设g 是2 - 连通的注意到，6 ( ) 和6 ( 厶) 为简单圈令 = i 【u l z t 2 让n ，f 2 = 【v 1 i ) 2 】，其中 为图g 的无界面 若存在边讹e ( g ) 一e ( f 1 ) ，j i ，则导出子图h = g 【 讹，u i + 1 ，坳) 】 是一个外平面图，l h i 3 若i h l = 3 ，h 显然包含一个顶点z 使得d a ( x ) = d h ( x ) = 2 若l h l 4 ，由引理2 5 ，h 包含不同于和呦的顶点z 使得 d g ( x ) = d f l ( x ) 2 ，于是( 1 ) 总成立若存在边地e ( c ) 一e ( 如) ，我们有类似 证明现在假设，e ( a ) 一( e ( ) ue ( ，2 ) ) 中每一条边有一个端点属于y ( ) ，另一 个端点属于y ( ，2 ) 若存在一个项点u i y ) 使得d g ( 乱i ) 5 ，则l t i 正好与y ( f x ) 上两个顶点 u i 一1 ，钍件l 相邻，且至少与y ( ，2 ) 上3 个顶点相邻，不妨设为，忱，( k z i + 1 ，这里下标的加法取为模 扎我们定义一个弦导出予图h = g ，“件l ，哟) 】显然，h 是一个2 - 连通的 1 0 2 2 夕 平面图的l ( 2 ，1 ) 一标号 外平而图如果i h l 三4 ，由引理2 5 ，存在两个相邻的顶点仳，移v ( a ) u i ，) 使得d g ( “) = 2 ，d gv ) 4 ，即( c 1 ) 成立于是，假设6 ( ) 的所有弦导出子图日 有l h l = 3 ，即为一个三角形同理假设，b ( f 2 ) 的所有弦导出子图也是三角形证 明分为下面两种情形： 情况la ( g ) 9 不失一般性，假设d g ( u 1 ) 9 那么， l i l u 2 ，“1 u n e ( ) 我们断言，u l 至多 和v ( y x ) u 2 ，) 中的u 3 或l t , n l 相邻，否则推出6 ( ) 有一个弦导出子图的 阶大于3 ，这是一个矛盾于是，让1 与y ( ，2 ) 巾的至少5 个顶点相邻，依序设为 v l ，优，v k ，v t ，1 i j k z 设p = v l v 2 v i 砚v t l v l 是b ( f 2 ) 中从v l 到v l 的一段路设，l p z ，是p 上的一个任意的内部顶点那么，吻 相邻于v p 一1 ，v p + 1 ，可能有u 1 除此以外，因为6 ( 厶) 的所有弦导出予图是三角形， 唧至多能和一2 或吻+ 2 相邻故d g ( ) 5 。如果p 有一个内部顶点是2 - 点，那 么( c 1 ) 成立否则，p 在g 中没有弦，它的每一个内部顶点必是3 点，即对所有的 2 p z 一1 ，z 1 e ( g ) ，我们得到子图( c 2 ) 情况2a ( g ) 8 如果g 有一个2 点，那么( c 1 ) 成立假设6 ( g ) 3 凶为( g ) 5 ，g 不是 图山引理2 7 ，推出6 ( a ) = 3 这隐含着6 ( ) 和6 ( 厶) 没有弦再一次，设u l 是g 的最大度点，则u l 必与6 ( 五) 中一段路上的所有顶点相邻，设为v l v 2 v k ， 其中k = d a ( u 1 ) 一2 若7 d a 0 1 ) 8 ，即5 k 6 ，那么v 2 ，v 3 ，v 4 是3 一点，我们 有子图( c 2 ) 若d g ( 札1 ) = 6 ，那么v 2 ，秽3 是3 一点，我们有子图( c 4 ) 若出( 乱1 ) = 5 ， 钉2 是3 一点，我们有子图( c 3 ) 引理证毕 2 2 l ( 2 ，1 ) 一标号数 引理2 9 3 1 对每一个a ( a ) 4 的图g ，有入2 ( g ) 2 ( g ) + ( g ) 一2 引理2 1 0 3 3 】每一个( g ) 4 的平面图g ，有入2 ( g ) 2 ( g ) 11 22 - 夕 平面图的l ( 2 ，1 ) 标弓 定理2 1 l 若g 为2 - 夕p 平面图，则儿( g ) ( g ) + 1 2 证明：设g 是一个2 - 夕 平面图在下面，我们简单记= ( g ) 如果2 ， a 2 ( g ) 4 ，结论显然 如果= 3 ，由引理2 9 ，a 2 ( g ) a 2 + a 一2 = 3 2 + 3 2 = 1 0 = a + 7 如果a = 4 ，注意到g 是平而图，由引理2 1 0 ，a 2 ( g ) s 2 = 1 6 = + 1 2 假设5 对g 的顶点数归纳证明如果 g l 6 ，结论显然成立设g 是 一个连通的2 - 夕f 平面图，满足5 ，i g i 7 如果g 包含一个l 度点口，令h = g v 显然，日仍是一个2 夕 平面图， 且a ( h ) 由归纳假设，日有一个( + 1 2 ) - l ( 2 ，1 ) 标号，带有一个标号 集合b = o ，1 ，+ 1 2 设盯( u ) 表示被限制在口上的标号数目那么， o ( v ) 3 + 一1 = a + 2 ，因此v 能被正常标号，被扩充到整个图g 假设 6 ( g ) 2 由引理2 8 ，g 含有子图形( c 1 ) - ( c 4 ) 我们分别来处理它们 ( c 1 ) 设u 3 是1 2 1 的不同于u 2 的邻点如果u 2 u 3 e ( g ) ，我们令h = g u l ； 如果u 2 u 3ge ( g ) ，我们令h = g 一钆1 + t 2 t 1 3 易见，日仍是一个2 - 夕 平面图，且 a ( h ) a 由归纳假设，日有一个( + 1 2 ) 一l ( 2 ，1 ) 标号，带有一个标号集合 b = o ，1 ，+ 1 2 注意到： a ( u 1 ) 3 + 3 + ( d v ( u 2 ) 一1 ) + ( d e ( u 3 ) 一1 ) 6 + ( 8 一1 ) + ( 一1 ) = + 1 2 ， 且i b i = + 1 3 ，缸1 能被正常标号 ( c 2 ) 如果v 2 v 4 e ( g ) ，我们令h = g v 3 ；甭则令h = g v 3 + v 2 v 4 那么， 日是一个2 一外平面图，且( 日) 由归纳假设，日有一个( + 1 2 ) 一l ( 2 ，1 ) 一标 号厂注意到： a ( v 3 ) 3 + 3 + 3 + ( d a ( 秽2 ) 一2 ) + ( d g ( v 4 ) 一2 ) + ( d c ( v 1 ) 一3 ) 9 + ( 3 2 ) + ( 3 2 ) + ( 一3 ) = + 8 ， u 3 能被正常标号 1 2 2 2 - 夕 平面图的l ( 2 ，1 ) 一标号 ( c 3 ) 如果w 2 w 4 e ( g ) 。我们令h = g w 3 ；否则令h = g 一蚴+ 埘2 讪那 么，是个2 - 夕 平面图，且a ( h ) 由归纳假设，日有一个( + 1 2 ) 一l ( 2 ，1 ) 一 标号，山5 ，我们有 a ( w 3 ) 3 十3 + 3 + ( d e ( 叫1 ) 一3 ) + ( d c ( 叫2 ) 一2 ) + ( d c ( 伽4 ) 一2 ) 9 + ( 5 2 ) + ( 5 2 ) + ( 5 3 ) = 1 7 + 1 2 ， 蚴能被正常标号 ( c 4 ) 如果x 2 x 4 e ( g ) ，我们令h = g x 3 ；否则令h = g - x 3 + x 2 x 4 那么， 日是一个2 夕 平面图，且a ( h ) 由归纳假设，日有一个( + 1 2 ) - l ( 2 ，1 ) - 标 号，由5 ，我f 门有 a ( x 3 ) 3 + 3 + 3 + ( d c ( z 1 ) 一3 ) + ( d g ( z 2 ) 一2 ) + ( d g ( x 4 ) 一2 ) 9 + ( 6 3 ) + ( 6 2 ) + ( 3 2 ) = 1 7 a + 2 ， x 3 能被正常标号 在每一种可能的情形，被扩充到原来图g 因此，入2 ( g ) sa + 1 2 定理证 毕 由定义，对每一个图g ，有a 2 ( g ) ( g ) + 1 定理2 1l 断言：每一个2 - 夕 、平 而图g 的l ( 2 ，1 ) 一标号数介于a ( c ) + 1 和( g ) + 1 2 之间我们觉得上界中的常 数1 2 不是最好可能的因此提出下面问题： 问题l 确定最小常数c 宰，使得每一个2 - 夕p 平面图g 有a 2 ( g ) ( g ) + 因为所有树图是2 - 夕 平面，又知存在无限多个树r 有a 2 ( t ) = ( r ) + 2 因 此，2 c + 1 2 1 3 3 广义p e t e r s e n 图的l ( d ，1 ) 一标号 本章主要考虑p e t e r s e n 图和广义p e t e r s e n 图的l ( d ，1 ) 标号问题对整数 n 3 ，广义p e t e r s e n 图p ( n ) 是一个3 一正则图，它是在两个n - 圈c x = v l v 2 v n 0 1 和c o = u l u 2 u n u l 之间加一个基数为佗的完美匹配后得到的图，其中。被称 为内圈，被称为外圈显然，著名的p e t e r s e n 图属于p ( 5 ) 此外，如果一个阶为 2 n 的3 正则图g 的顶点集合能够被剖分为两个长为佗的圈，那么g p ( 礼) 引理3 1 【蚓对d21 和每一个图g ，有知( g ) a 2 + ( d 一1 ) a g e o r g e s 署t l m a u r o 3 0 】研究了广义p e t e r s e n 圈i 约l ( 2 ，1 ) 一标号问题，得到以下结 引理3 2 【3 0 】对每一个广义p e t e r s e n g ，a 2 ( g ) 9 ；且a 2 ( g ) = 9 当且仅当g 同 构于p e t e r s e n 图 事实上，由引理3 1 立即推出，每一个3 - 正则图g 有扎( g ) 3 d + 6 因此是对 广义p e t e r s e n 图p ( n ) 有沁( p ( 几) ) 3 d + 6 本文将改进这个上界到3 d + 3 id + 2 ， 若佗三0 ( r o o d4 ) ； 儿( g ) = m i n 2 d ，d + 3 ) ，若n 兰2 ( m o d 4 ) ； i - 2 d ， 若n 为奇数 3 广义p e t e r s e n 图的l ( d ，1 ) 一标号 图3 1p e t e r s e n 图 定理3 1 设d 3 ，i ) l j j p e t e r s e n i 蛩g 有入d ( e ) = 2 d + 3 证明：假设g 的外5 一圈上的点依序为钍1 ，“2 ，“3 ，u 4 ，“5 ，内5 圈上与棚邻的点为 ( 见图3 。1 ) 首先给出g 的一个( 2 d + 3 ) 一l ( d ，1 ) 一标号如下：让l ，i t 2 ，u 3 ， u 4 ，u 5 分别标2 d + 1 ，3 ，2 d + 2 ，d + 2 ，2 ；v 1 ，耽，v 3 ，v 4 ，v 5 分别标d + l ，2 d + 3 ，o ，1 ，d + 3 因此，a d ( g ) 2 d + 3 为了证明k ( g ) 2 d + 3 ，我们假设k ( g ) 2 d + 2 设，是g 的一 个( 2 d + 2 ) l ( d ，1 ) 一标号，应用标号0 ，1 ，2 ，2 d + 2 断言3 1 对任何v y ( g ) ，y ( v ) 隹 3 ，4 ，d 一1 ，d + 3 ，d + 4 ，2 d 一1 ， 假若小然，由g 和标号的对称性，我们可以假设f ( u 1 ) 3 ，4 ，d 一1 ) 由引理3 4 可知，包含1 1 , l 的任何奇圈g 上至少有一点的标号不大于2 ，否则 m a x f ( v ) v y ( c k ) ) 2 d + 3 ，矛盾显然，5 一圈u l v l 0 4 u 4 u 5 i 上标号不大于2 的点只能为铂，锄之一，5 圈u l u l 地“3 札2 u l