（应用数学专业论文）有邻域限制的图染色问题及图的l21标号.pdf

山东师范大学硕士学位论文 有邻域限制的图染色问题及图的l ( 2 ，1 ) 一标号 刘晓晓 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 图的染色问题是图论研究中一个活跃的领域，因此各类染色问题被相继提出并 加以发展应用，赖宏建等人在2 0 0 6 年提出了条件染色图的标号问题就是图的染 色问题的推广，其理论研究背景是频道分配问题g r i g g s 和y e h 在1 9 9 2 年提出了 l ( 2 ，1 ) 一标号问题，作为标号问题的另一种推广，孙磊老师于2 0 0 8 年提出了邻域限 制标号问题 条件染色是传统的点染色在理论上的自然地推广，是在文献【2 】中首次提出的 对于整数k 0 和r 0 ，图g 的一个正常( k ，r ) 一染色【2 】是个满足下面两个条件 的映射c ：v ( a ) 一 l ，2 耐， ( 1 ) 若让t ，e ( g ) ，贝! c ( u ) c o o ； ( 2 ) 对任意的口y ( g ) ，i c ( n g ( v ) ) i m i n l n g ( v ) l ，r ) 对于固定的7 ，使g 有一个正常的( 七，7 ) 一染色的最小的k 是图g 的第r 个条 件色数，记为骼( g ) 由条件色数的定义很显然的得到x l ( g ) = x ( g ) 作为频率设置问题的一个变形，g r i g g s 和y e h 在1 9 9 2 年提出了l ( 2 ，1 ) 一标 号问题图g 的一个l ( 2 ，1 ) 一标号【1 】是一个满足下面两个条件的映射c ：v ( g ) o ，1 ，2 静) ， ( 1 ) 对任意的t ，可y ( g ) ，若d ( u ，影) = 1 ，则ic ( u ) 一c ( v ) l 2 ； ( 2 ) 对任意的，可y ( g ) ，若d ( u ，秽) = 2 ，则lc ( u ) 一c ( v ) i 之1 当所有的标号都小于等于k 时，称图g 有一个七一l ( 2 ，1 ) 一标号则使得图g 有 一个k l ( 2 ，1 ) - 标号的最小的正整数k 称为图g 的l ( 2 ，1 ) 一标号数，记为入( g ) 令c 是图g 的一个的a ( g ) 一l ( 2 ，1 ) - 标号令c - - 1 ( z ) = 【 v ( a ) ic ( v ) = t ) 且令 ic - 1 ( t ) i 表示c - 1 ( i ) 的基数若对于一个整数h ( 0 h 0 ，图g 的一个一二1 一标号是一个满足下面两个条件的映, 2 1 山东师范大学硕士学位论文 射c ：v ( g ) 一 o ，1 ，2 七) ， ( 1 ) 任意的影y ( 回，若d ( u ， ) = 1 ，则jc ( 让) 一c ( 砂) j 21 ； ( 2 ) 任意的u ，t ，v c g ) ，若存在t t 7 y ( g ) ，使得牡， n o ( w ) ，则ic ( u ) 一c ( u ) i 2 则使得图g 有一个k l 1 。2 标号的最小的正整数k 称为图g 的邻域限制标号数， 记为l 1 ，2 ( g ) 令c 是图g 的个的七一l l ，2 一标号令c - 1 ( i ) = u v ( c ) ic ( u ) = 1 ) 且令ic - - 1 ( i ) i 表示c - 1 ( i ) 的基数若对于一个整数h ( o h k ) 满足ic 一1 ( ) i = 0 ， 则称h 为c 的一个洞 本文中z x ( g ) 表示图g 的最大度，6 ( g ) 表示图g 的最小度，d ( 乱，u ) 表示u ， 两点在图g 中的距离，g a ( v ) 表示t ，在图g 中的邻域在本文的第二章我们主要 得到了以下结论 引理2 1 1 图g 是任意简单图，则l 1 ，2 ( c ) 2 ( a ( g ) 一1 ) 引理2 1 2 图g 是任意简单图，且i l ，2 ( e ) = 2 ( a ( g ) 一1 ) 则任意的最大度点 t ，c ( 可) 兰l ( m o d 2 ) ，且任意的u ( ) ，c ( u ) = 2 i ( i = o ，1 ，2 a c c ) 一1 ) 定理2 1 3 若图g 中有两个最大度点相邻，则l 1 ，2 ( g ) 2 a ( g ) 一1 定理2 1 4 若正则图g 中有奇圈且4 ，则l 1 ，2 ( g ) 2 a ( g ) 定理2 1 5 图g 是圈，则当j 矿( 回i - o ( m o d 4 ) 时，l 1 ，2 ( g ) = 3 ；否则，l 1 ，2 ( g ) = 4 定理2 1 6 设图g 是k 一退化图，4 且无三角，则2 ( a 一1 ) l t ，2 ( 0 ) a ( 6 k 一3 ) + 七一3 k 2 、 定理2 2 1 设图g 是树，( g ) 23 ，且图g 中有两个最大度点相邻，则 l 1 ，2 ( g ) = 2 a ( g ) 一1 定理2 2 3 设图g 是树，a ( g ) 3 ，若图g 中无最大度点相邻且任意两个最 大度点的距离为偶数，则l 1 ，2 ( g ) = 2 ( ( g ) 一1 ) 定理2 2 4 设图g 是树，( g ) 4 ，若存在一条包含所有最大度点的路则 当图g 中无两个最大度点不相邻且存在两个最大度点的距离为奇数时，l l ，2 ( g ) = 2 ( a ( g ) 一1 ) 定理2 2 5 设图g 是树，a ( g ) 3 ，若图g 中只有一个最大度点，则l l ，2 ( g ) = 2 ( a ( c ) 一1 ) 我们证明了当c 是g 的个最小的邻域限制标号，且h 是c 的一个洞，图g 具有的下述性质 性质2 3 1 图g 是任意简单图，若c 是g 的一个最小的邻域限制标号，且h 2 山东师范大学硕士学位论文 是c 的一个洞，则h 一1 ，h + 1 都不是c 的洞 性质2 3 2 令c 是g 的一个最小的邻域限制标号，h 是c 的一个洞若 ic - - 1 ( 忍一1 ) l 2 或lc - 1 m + 1 ) i 2 且c ( 乱) = h 一1 ，c ( v ) = 危+ 1 ，则肯定存在一 点z 满足d ( u ，z ) 2 且c ( z ) = h + 1 或一点满足a ( v ，矽) 2 且c ( u ) = h 1 性质2 3 3 图g 是任意简单图且无三角，令c 是图g 的一个最小的邻域限制 标号，且h 是c 的一个洞若对任意的标号i ，满足lc , - 1 ( t ) i 2 ，则若c ( v ) = h 一1 或危+ 1 ，则肯定存在两点t ，1 ， 0 2 满足a ( v ，移1 ) = 1 ，d ( 口，秒2 ) = 2 , c ( v t ) = c ( v 2 ) = h + l 或 h 一1 且吮l y e ( v 1 ) 性质2 3 4 图g 是任意简单图且无三角，令c 是g 的一个最小的邻域限制标 号，且h 是c 的一个洞若存在路 1 1 , 0 0 0 ，满足c ( 让) = h 一1 ，c ( v ) = h + 1 且任意的z 满足a ( u ，z ) = 2 ，但c ( z ) h + 1 且任意的1 t 满足d ( 可，可) = 2 ，但c ( u ) h 一1 则此时 lc - 1 ( c ( o ) ) i = 1 性质2 1 3 5 图g 是任意简单图且无三角，令c 是g 的一个最小的邻域限制标 号，h 是c 的一个洞，且lc - - 1 仰一1 ) i _ 1 ，lc - - 1 + 1 ) i 2 若令c ( u ) = 7 , 一1 ， 则对任意的仇满足c m ) = h + 1 ，存在路u 叫t 忱若任意的 o i 满足d ( u ， 0 i ) 1 ，则 ic - 1 ( c ( 桃) ) j = 1 或有且仅有一个仉满足d ( u ，v i ) 1 g 是一个简单图， v ( g ) = v l ，耽，a z 2 】的点集和边集如下定义： y ( g 【如】) = l ， 0 2 ， o n ，w ：，选，t 7 二) ，e ( g 【如1 ) = e ( a ) u 【锄知：，”：勘l 优呦e ( g ) ) ， 则g 阮】称为g 的点分裂图【绷令g = ( y ( g ) ，e ( g ) ) ，v ( a ) = 口1 ，眈，蚀， ，m 一 构造图m ( g ) 的点集和边集是如下定义的，y ( m ( g ) ) = v l ，1 1 1 n ，乱1 ，t 7 ， e ( m ( g ) ) = 蛳v l i = 1 ，2 死) u 蚴i e ( g ) ，m 一构造图在研究图染色问题 的临界性上有重要应用在本文的第三章我们讨论了图g 与其分裂图c h 】的条件 色数的关系及图g 与其m 一构造图m ( g ) 的条件色数的关系，给出了几类特殊图 的条件色数 定理3 1 1 图g 与其分裂图g 阮】的条件色数的关系如下， ， i骼( g ) = 骼( g ) ；若r 6 ( g ) ， x r ( g ) x ，( g 【如】) 2 x r ( g ) ；若6 ( a ) s ，2 a ( c ) ， i x ，( g 【如】) = 2 x ，( g ) ；若，- 2 a ( c ) 定理3 2 1 若整数r 满足0 0 ，t h es m a l l e s tks u c ht h a tgh a sap r o p e r ( k ，r ) c o l o r i n gi s t h er t ho r d e rc o n d i t i o n a lc h r o m a t i cn u m b e ro fg ，d e n o t e d 骼( g ) b yt h ed e f i n r i o no f x r ( g ) ，i tf o l l o w si m m e d i a t e l yt h a t ) ( 1 ( g ) = ) ( ( g ) a sav a r i a t i o no ff r e q u e n c ya s s i g n m e n tp r o b l e m ，i n1 9 9 2g r i g g sa n dy e hp r o p o s e dt h e l ( 2 ，1 ) - l a b e l l i n g al ( 2 ，1 ) - l a b e l l i n go fg r a p hg i sd e f i n e d 嬲af u n c t i o ncf r o mt h ev e r t e x s e tv ( a ) t ot h es e to fa l ln o n n e g a t i v ei n t e g e r ss u c ht h a tic ( u ) 一c ( 御) i 2f fd ( u ，口) = l a n d ic ( 乱) 一c ( v ) i 1i fd o , ，口) = 2 ak l ( 2 ，1 ) - l a b e l l i n gi sa nl ( 2 ，1 ) 一l a b e l l i n gs u c ht h a t n ol a b l ei sg r e a t e rt h a n 七t h el ( 2 ，1 ) - l a b e l l i n gn u m b e ro fg ，d e n o t e db y 入( g ) ，i st h e s m a l l e s tn u m b e rks u c ht h a tgh a sa 七一l ( 2 1 ) - l a b e l l i n g i f ci sa a ( g ) - l ( 2 ，1 ) - l a b e l l i n go f g r a p hg ，t h e nc - - 1 ( z ) = 和v ( g ) ic ( v ) = i ) a n d t h ec a r d i n a ln u m b e ro flc - 1 ( t ) ii sd e n o t e db yc - 1 ( i ) w ec a l lt h ei n t e g e rh ( 0 h 七) ，a 5 山东师范大学硕士学位论文 h o l eo fci fa n do n l yi fic - - 1 ( ) | = 0 t h eh o l ei n d e xo fag r a p hg ，d e n o t e dp ( g ) ，i st h e m i n i m u mn u m b e ro fh o l e st a k e no v e ra l la ( g ) 一i ( 2 ，1 ) - l a b e l l i n go fg r a p hg a 七一l 1 ，2 - l a b e l l i n go fg r a p hg i sd e f i n e d 笛af u n c t i o nc ：v ( a ) 一 o ，1 ，2 七) s u c ht h a tb o t ho ft h ef o l l o w i n gh o l d ： ( 1 ) i f 伽e ( c ) ，t h e nc ( u ) c ( v ) ；a n d ( 2 ) t h e r ei sa v e r t e x 伽s u c ht h a t7 2 ，t 7 n o ( w ) ，t h e n ic ( u ) 一c ( v ) l 2 t h e l a b l e l l i n gn u m b e r sw i t hac o n d i t i o no nn e i g h b o r h o o do fg ，d e n o t e db yl 1 ，2 ( g ) ， i st h es m a l l e s tn u m b e rks u c ht h a tgh a sak l 1 ，2 - 1 a b e l l i n g i fci sa 七一l t ，2 - l a b e l l i n go fg r a p hg ，t h e nc - 1 ( ) = 口v ( c ) ic ( ) = t ) a n d t h ec a r d i n a ln u m b e ro fc - 1 ( i ) i sd e n o t e db yic - i ( i ) i w ec a l lt h ei n t e g e rh ( 0 0 和r 0 ，图g 的一个正常( 后，r ) 一染色是一个满足下面两个条件的 映射c ：v ( g ) 叫 1 ，2 七】， ( 1 ) 若伽e ( g ) ，则c ( u ) c ( v ) ( 2 ) 对任意的t 7 y ( g ) ，i c ( n a ( v ) ) l m m i n c ( v ) l ，r ) 对于固定的r ，使g 有一个正常的( 凳，r ) 一染色的最小的凳是图g 的第7 1 个条 件色数，记为骼( g ) 在文章【2 】中证明了命题2 1 2 ( i ) x r ( g ) 静一l ( a ) 2 ) ( 2 ( g ) x ( g ) ( 1 0 i v ( a ) l x ，( g ) m i n r ，( g ) 】+ 1 给出了树，二部图，圈的条件色数，讨论了在什么条件下x 2 ( g ) = x ( g ) ，并给出了 x ，( g ) 的上界 相继的李学良，姚祥妹，周文礼等人在文章【3 】，【4 】中证明了条件染色问题是 n p 一困难的，研究了无爪图的2 条件3 染色问题。并把条件染色的定义推广到了 条件边染色在文章【5 】中丁超，樊锁海，赖宏建证明了定理1 【5 】：骼( g ) a 2 + 1 ，等 号成立时当且仅当图g 是m o o r e 图， 1 2基本概念与符号 山东师范大学硕士学位论文 一个图g 是指一个有序对g = ( y ( g ) ，e ( g ) ) 其中v ( g ) 是顶点集，e ( g ) 为 边集，e c c ) 中的边为v ( g ) 中两不同顶点的无序对若v ( c ) 中的两顶点u ，t ，之 间有边，则称两顶点相邻且互为邻点，边记为伽，称边缸u 关联u ，可，边u u 的端点 为缸，v 若两边有公共端点，则称两边相邻且互为邻边端点重合为一点的边称为 环；若两边有相同的两个端点，则称它们为多重边一个图为简单图，若它既没有 环也没有多重边本文所讨论的图均为简单有限图 h ( v 7 ，) 称为图g ( ve ) 的子图，若y 7 k e 假设是y 的一 个非空子集，以y 7 为顶点集，以两端点均在y 中的边的全体为边集所组成的子 图，称为g 的由导出的子图，记为c v ，】g e 表示从g 中去掉边e 得到的 图对任意 y ( g ) ，d ( ) 表示顶点t ，在g 中关联的边数，称为钐的度定义 6 ( c ) = m i n a ( 口) lu v c c ) ，( g ) = m a x d ( v ) i 口v c c ) ，分别称为g 的最小度和 最大度v ( c ) 的子集s 称为独立集，若s 中的任意两顶点均不相邻顶点数最多 的独立集称为g 的最大独立集，顶点个数称为独立数，记为q ( g ) 简单图g 的一 个团是指顶点集的一个子集s ：使得g 旧是完全图顶点数最多的团称为g 的最 大团，顶点个数称为g 的团数，记为u ( g ) 设g 是个简单图，任意两个顶点。，y 的距离d ( z ，y ) 是z y 路长的最小值特别的，如果没有z y 路，则d ( z ，y ) = 图g 的直径d i a m ( g ) 定义为d i a m ( g ) = m 凹础d ( z ，) ( z ，y y ( g ) ) ，图g 的半径 r a d ( g ) 定义为r a d ( g ) = m i n x m a x d ( z ，) ( z ，y v c g ) ) 图g 的最小圈长称为图g 的围长若图g 的直径为d 围长为2 d + 1 ，则称图g 为m o o r e 图 所有顶点均两两相邻的简单图称为完全图，n 个顶点的完全图记为设 ，是图g 的两顶点独立集，若v c c ) = u ，n = d ，且图g 的每条边一个 端点在中，一个端点在场中，则称g 为二部图或偶图进一步，若中的每 个顶点与k 中的每个顶点相邻，则称g 为完全二部图，此时若iki = n ，ik | - m ， 则记为m 图g 的一个( 正常) 七一染色是将k 种颜色分配给g 的顶点集y ( g ) ，使得相邻 两顶点的颜色不同图g 的色数记为x ( g ) ，是使得图g 存在( 正常) 七一染色的最小 的正整数k 类似地，图g 的一个( 正常) 七一边染色是将k 种颜色分配给g 的边集 e c g ) ，使得有公共端点的两边的颜色不同图g 边色数记为( g ) ，是使得图g 存 在( 正常) 七一边染色的最小的正整数k 本文所用符号与术语与文献【3 8 】，【3 9 】中一致，本节未介绍的其它图论术语，将 在必要时予以阐述 1 2 山东师范大学硕士学位论文 第二章图的邻域限制标号 图的邻域限制标号问题是图的染色问题的推广，它有着强烈的应用背景和和很 好的理论探讨价值在图上，用点表示无线电发射台，两个顶点之间存在一条边当 且仅当对应的发射台相互干扰，用非负整数表示频率如果在频道分配问题中若要 求较高的灵敏度，使得干扰同一个无线电发射台的无线电发射台之间能够明显的区 别开，那么干扰同一个无线电发射台的无线电发射台之间的频道就不能相差太小 对应于图上也就是要求同一个点的邻点的标号之间不同相差太小，根据这一问题， 孙磊老师在2 0 0 8 年提出邻域限制标号问题 图的领域限制标号问题与图的l ( 2 ，1 ) 一标号问题是不同的图g 的l ( 2 ，1 ) 一 标号是指从其顶点集v ( a ) 到非负整数集的一个映射，满足若d ( 牡，勘) = 1 ，则i f ( - ) 一f ( v ) i 2 ；若d ( u ，t ，) = 2 ，则l ，( u ) 一l ( v ) i 1 所以图的l ( 2 ，1 ) - 标号是对距 离为1 和2 的两点的标号有特殊的要求，而图的领域限制标号问题是对同一个点 的邻点的标号有特殊的要求当两个点u ，口的距离为2 时，乱，锄肯定同一个点的邻 点，但是当两个点心，u 的距离为l 时，缸，口仍然可能是同一个点的邻点所以图的 邻域限制标号问题不是l ( 2 ，1 ) 一标号问题条件的简单的置换 但是图的邻域限制标号问题和图的l ( 2 ，1 ) 一标号问题是有联系的若c 是图g 的一个a ( g ) 一1 ( 2 ，1 ) 一标号，定义一个映射，对任意的口y ( g ) ，令，( 口) = 2 c ( v ) 则显然，是图g 的一个2 入( g ) 一邻域限制标号，所以l 1 ，2 ( a ) 2 a ( g ) 2 0 0 3 年在 文章【9 】9 中证明了a ( g ) 的上界是2 + 一1 ，所以l l 。2 ( g ) 的上界显然小于等于 2 ( 2 + a 一1 ) 在本章我们主要研究了图的邻域限制标号问题的下界和退化图的上 界，树的邻域限制标号和邻域限制标号问题的一些性质，并且由第二节的定理说明 给出的这些下界是最好可能的 2 1图的邻域限制标号问题的上界和下界 引理2 1 1 图g 是任意简单图，则l l ，2 ( a ) 2 ( ( g ) _ 1 ) 证明：假设命题不成立，l i ，2 ( a ) 2 a ( a ) - 3 则应该存在一个映射c ：v ( a ) 啼 o ，1 ，2 2 ( g ) 一3 ) ，对任意的让，t ，y ( g ) ，若d ( 似，钞) = 1 ，则ic ( 让) 一c ( 口) 1 21 ；对任 1 3 山东师范大学硕士学位论文 意的u ，t ，y ( g ) ，存在伽y ( g ) ，使得u ，t 7 n g ( w ) ，则ic m ) 一c ( t ，) i 2 不妨设d ( v ) = ( g ) ，则其任意两个邻点的标号至少要差2 此时0 , 1 ，2 2 ( g ) 一 3 共a ( g ) 一1 个奇数和a ( g ) 一1 个偶数，显然若标号中只有奇数或只有偶数无法 给a ( g ) 个点标号若存在k ( 0 k ( g ) 一1 ) 个点的标号为奇数，则由定义的要 求知，至少个偶数标号不能用，所以至多k + ( ( g ) 一1 ) 一k = a ( g ) 一1 个标号 可以用，无法给a ( a ) 个点标号 所以假设不成立，原命题成立，若图g 最大度为( g ) ，则己1 ，2 ( g ) 2 ( ( g ) 一1 ) 引理2 1 2 图g 是任意简单图，且l 1 。2 ( g ) = 2 ( a ( g ) 一1 ) 则任意的最大度点 秽，c ( t ，) 兰l ( r n o d 2 ) ，且任意的u n g ( v ) ，c ( u ) = 2 i ( i = 0 ，1 ，2 a ( g ) 一1 ) 证明：令c 是图g 的2 ( a ( g ) 一1 ) 一三1 , 2 一标号任意的最大度点彭，其( g ) 个 邻点的标号只能从0 ，1 ，2 2 ( a ( g ) 一1 ) 中选，一共( g ) 个偶数a ( g ) 一1 个奇数 且按邻域限制标号的定义知，任意的z ，y g ( ) ，ic ( z ) 一c ( 2 ，) l 2 若存在七( 七1 ) 个点的标号为奇数，则按邻域限制标号的定义知，至少+ 1 个偶数标号不能用， 所以至多七+ ( g ) 一( k + 1 ) = a ( g ) 一1 个标号可以用，无法给a ( g ) 个点标号 由上述证明知，对任意的最大度点t ，其a ( g ) 个邻点的标号为2 i ( i = 0 ，1 ，2 a ( g ) 一1 ) 从0 ，1 ，2 2 ( a ( g ) 一1 ) 中一共a ( g ) 个偶数a ( c ) 一1 个奇数，所以c ( v ) 只能为奇数 定理2 1 3 若图g 中有两个最大度点相邻，则三l ，2 ( g ) 2 a ( g ) 一1 证明：假设命题不成立，即若图g 中有两个最大度点相邻，但三l 。2 ( g ) 2 ( a 一1 ) ， 且由引理2 1 1 知l i ，2 ( g ) 2 ( a 一1 ) ，所以l t ，2 ( g ) = 2 ( 一1 ) 下面定义一个映射c ：v ( g ) 一 o ，1 ，2 2 ( a ( g ) 一1 ) ) ，满足对任意的u ，t 7 矿( g ) ，若d ( t i ，影) = 1 ，则jc ( 一c ( t ，) l 1 ；对任意的t ，t ，y ( g ) ，存在w y ( g ) ，使 得t ，口g ( t 1 7 ) ，则ic ( u ) 一c 0 ) i 2 若伽e ( c ) 且d ( u ) = d ( u ) = ( g ) ，则对于u 的个邻点只能从0 , 1 ，2 2 ( ( g ) 一 1 ) 中选一个标号且对任意的s ，t g ( u ) ，ic ( s ) 一c ( t ) i 2 所以对任意的s g ( u ) ，c ( s ) 三0 ( m o d 2 ) 因为0 , 1 ，2 2 ( ( g ) 一1 ) 一共( g ) 一1 个奇数和a ( c ) 个偶 数，若存在k ( 0 奄a ( c ) 一1 ) 个点的标号为奇数，则由定义的要求知，至少七+ 1 个偶数标号不能用，所以至多后+ a ( g ) 一( k + 1 ) = ( g ) 一1 个标号可以用，无法给 a ( g ) 个点标号又因为t ，g ( 牡) ，所以c ( ) 兰o ( m o d 2 ) ，且0 , 1 ，2 2 ( ( g ) 一1 ) 一 1 4 山东师范大学硕士学位论文 共a ( g ) 个偶数，所以c ( u ) 兰l ( m o d 2 ) 同理可证c ( 口) 兰l ( m o d 2 ) ，与c ( ) 兰o ( m o d 2 ) 矛盾 所以若图g 中有两个最大度点相邻，则l 1 。2 ( g ) 2 a 一1 定理2 1 4 若正则图g 中有奇圈且3 ，则l 1 ，2 ( g ) 2 ( g ) 证明：因为g 是正则图，所以图g 中有两个最大度点相邻，由定理2 1 3 知， l 1 ，2 ( c ) 2 a ( g ) 一1 假设命题不成立，若正则图g 中有奇圈，l 1 2 ( g ) 2 a ( g ) 一1 综上所述l 1 ，2 ( g ) = 2 a ( g ) 一1 下面定义个映射c ：v ( v ) 一 o j1 ，2 2 a ( g ) 一1 ) ，满足对任意的t ，秒y ( g ) ， 若d ( u ，t ，) = 1 ，则lc ( u ) 一c ( u ) i 1 ；对任意的t ，们y ( g ) ，存在t 1 7 y ( g ) ， 使得t ，t i n g ( w ) ，则ic ( u ) 一c ( t j ) l 2 在图g 中肯定存在一个点御，使得 c ( v ) = 0 ，否则所有点的标号均大于0 此时定义一个新的映射d ，对任意的勘y ( g ) ， 令c ，( 钉) = c ( ) 一1 显然c ，是一个v ( v ) 一 o ，1 ，2 2 ( a ( g ) 一1 ) ) 的正常的 2 ( ( g ) 一1 ) 一l 1 ，2 一标号，与l t ，2 ( g ) ；2 a ( g ) 一1 矛盾 下面关于点的标号的奇偶性进行分类讨论但是对于标号0 和2 a ( g ) 一1 和其 他情形的证明方法略有不同，所以首先对标号为0 和2 ( g ) 一1 进行讨论 ( 1 ) 若点t i 满足c ( v ) = 0 ，则其a ( c ) 个邻点的标号只能为1 , 3 ，5 2 a ( g ) 一1 事 实上按照定义任意的z ，可n g ( v ) ，ic ( z ) 一c ( y ) l 2 且因为0 , 1 ，2 2 ( g ) 一1 中一 共( g ) 个奇数，a ( g ) 一1 个偶数若存在k 个点的标号为偶数，则由定义的要求 知，至少k + 1 个奇数标号不能用，所以至多k + ( g ) 一( k + 1 ) = a ( g ) 一1 个标号 可以用，无法给( g ) 个点标号 情形( 1 1 ) 若对任意的z n c ( v ) 与影都有公共的邻点，则按照定义ic ( z ) 一 c ( 钞) i 2 ，所以标号1 不能用，则无法给a ( g ) 个点标号 情形( 1 2 ) 若至少有一个z n g ( v ) 与t ，没有公共的邻点，下面分两种子情况 讨论 情形( 1 2 1 ) 若不是任意的y b ( 口) 与郇都没有公共的邻点，但至少有一个 z g ( ) 与口没有公共的邻点，则按照邻域限制标号的定义ic ( x ) 一c ( t ，) 1 21 ，显 然此时只有令c ( z ) = 1 ，其他的z n g ( v ) 从3 , 5 2 a ( g ) 二1 任取一个标号才可以 正常标号也就是存在两点z ，y n g ( v ) 满足x y e ( g ) ，且c ( z ) = 2 i 一1 ，c ( ! ) = 巧一t ( 2 t ，j ( g ) ) 情形( 1 2 2 ) 若对任意的z g v ( v ) 与t ，都没有公共的邻点，则按照定义i 1 5 山东师范大学硕士学位论文 c ( z ) 一c ( 口) i 1 ，所以z 可以从1 , 3 ，5 2 a ( g ) 一1 任取一个标号 ( 2 ) 对于点 ，若c ( ”) = 2 a ( g ) - 1 ，则其( g ) 个邻点的标号只能为0 , 2 ，4 2 ( ( g ) 一 1 ) 事实上按照定义任意的z ，y n o ( v ) ，ic ( z ) 一c ( ) i 2 且因为任意的u n g ( v ) 的标号只能从0 , 1 ，2 2 ( a c e ) 一1 ) 选，共( g ) 个偶数，a ( c ) 一1 个奇数若存在 k 个点的标号为奇数，则由定义的要求知，至少k + 1 个偶数标号不能用，所以至 多k + a ( c ) 一( k + 1 ) = ( g ) 一1 个标号可以用，无法给a ( c ) 个点标号 情形( 2 1 ) 若对任意的z n c ( v ) 与秽都有公共的邻点，则按照定义ic ( z ) 一 c ( 口) l 2 ，所以标号2 ( a ( g ) 一1 ) 不能用，则无法给a ( g ) 个点标号 情形( 2 2 ) 若至少有一个z n c ( v ) 与移没有公共的邻点，下面分两种子情况 讨论 情形( 2 2 1 ) 若不是任意的y n g ( v ) 与t ，都没有公共的邻点，但至少有一个 z n g ( v ) 与口没有公共的邻点，则按照邻域限制标号的定义ic ( z ) 一c ( t 7 ) i 1 ，显 然此时只有令c ( z ) = 2 ( a ( g ) 一1 ) ，对于其他的y n g ( v ) 从o ，2 ，4 2 ( a ( c ) 一2 ) 中 任取一个标号才可以正常标号也就是存在两点z ，y n g ( v ) 满足x y e ( g ) ，且 c 0 ) = 2 i ，c ( ) = 2 j ( o i ，歹( a ( g ) _ 2 ) 情形( 2 2 2 ) 若对任意的z n g ( v ) 与t ，都没有公共的邻点，则按照定义f c ( z ) 一c ( 移) i 1 ，所以z 可以从o ，2 ，4 2 ( a ( g ) 一1 ) 中任取一个标号 ( 3 ) 对于点t ，若c ( ) = 2 i 一1 ( 1 i ( g ) ) ，则其a ( g ) 个邻点的标号只能为 0 , 2 ，4 2 ( ( g ) 一1 ) 事实上因为任意的u n c ( v ) 的标号不能为2 a ( g ) 一1 ，因为若 c ( t ) = 2 a ( g ) 一1 ，则任意的t ，n c ( u ) 的标号只能为偶数所以任意的u n g ( v ) 的 标号只能从0 , 1 ，2 2 ( a ( c ) 一1 ) 中选一个，共( g ) 个偶数，( g ) 一1 个奇数且按 照定义任意的z ，矽n o ( v ) ，ic ( z ) 一c ( 矽) i 2 ，所以若存在七个点的标号为奇数，则由 定义的要求知，至少k + 1 个偶数标号不能用，所以至多k + a ( g ) 一( k + 1 ) = ( g ) 一1 个标号可以用，无法给a ( g ) 个点标号 所以此时否定了情形( 1 2 1 ) ，因为情形( 1 2 1 ) 中存在两点z ，y n g ( v ) 满足 x y e ( g ) ，且c ( 。) = 2 i 一1 ，c ( ) = 2 j 一1 ( 9 i ，j ( g ) ) ，与( 3 ) 的证明矛盾也就 是若点t 7 满足c ( 口) = 0 ，只有情形( 1 2 2 ) 才可以正常标号 情形( 3 1 ) 若至少有a ( g ) 一1 个z n g ( v ) 与u 都有公共的邻点，则按照定义 lc ( z ) 一c ( 口) l 2 ，所以标号2 i ，2 i 一2 不能用，则无法给( g ) 个点标号 情形( 3 2 ) 若至少有两个z ，矽n c ( v ) 与口没有公共的邻点，下面分两种子情 况讨论 1 6 山东师范大学硕士学位论文 情形( 3 2 1 ) 若不是任意的u n g ( v ) 与 都没有公共的邻点，但至少有两个 z ，y n c ( v ) 与口没有公共的邻点，则按照邻域限制标号的定义lc ( x ) 一c ( 移) l 1 且ic ( ) 一c ( v ) i 1 ，此时令c ( z ) = 2 i ，c ( y ) = 2 i 一2 对于其他的z n g ( v ) 可 以从 o ，2 ，4 2 ( a ( o ) 一1 ) ) 中任取一个标号也就是存在两点z ，y n c ( v ) 满足 x y e ( g ) ，且c ( z ) = 2 k ，c ( g ，) = 2 1 ( 0 k ，2 ( a ( c ) 一1 ) ，k ，z i ，i 一1 ) 情形( 3 2 2 ) 若对任意的z n v ( v ) 与t ，都没有公共的邻点，则按照定义l c ( z ) 一c ( 移) i 1 ，所以z 可以从0 , 2 ，4 2 ( a ( c ) 一1 ) 中任取一个标号 ( 4 ) 对于点口，若c ( v ) = 2 j ( 1 j ( g ) ) ，则其a ( c ) 个邻点的标号只能为 1 , 3 ，5 2 a ( g ) 一1 事实上因为根据上述的证明若c ( t 1 ) = 2 i 一1 0 = 1 ，2 ，3 ( g ) ) ， 则其a ( g ) 个邻点的颜色为0 , 2 ，4 2 ( ( g ) 一1 ) 故若c ( t ) = 2 i 一1 g = 1 ，2 ，3 ( g ) ) ， 则其邻点中肯定有标号巧即若c ( 钐) = 2 j ( 1 j i ( g ) ) ，则其a ( g ) 个邻点的标号 只能为1 , 3 ，5 2 a ( g ) 一1 所以此时否定了情形( 2 2 1 ) 和情形( 3 2 1 ) ，因为上述情形中存在两点z ，y g ( u ) 满足x y e ( g ) ，且c ( x ) = 2 i ，c ( y ) = 2 j ( o t ，歹( a ( g ) 一2 ) ，与( 4 ) 的证明矛 盾也就是若点口满足c ( v ) = 2 a ( g ) 一1 ，只有情形( 2 2 2 ) 才可以正常标号；若点 满足c ( 口) = 2 i 一1 ( i ( g ) ) ，只有情形( 3 2 2 ) 才可以正常标号且由上述证明知若 点t j 满足c ( t ，) = 2 j ( 1 歹 ( g ) ) ，则只有任意的z n e ( v ) 与t ，都没有公共的邻点 时，才可以正常标号否则存在两点z ，y n g ( v ) 满足x y e ( g ) ，且z ，y 的标号为 奇数，但上述证明说明若c ( 彻) 为奇数，则其邻点的标号肯定是偶数 在正则图中，若l 1 ，2 ( g ) = 2 a 一1 ，删e ( g ) ，则c ( u ) ，c ( v ) 一定一奇一偶正则 图中有三圈，在前面的证明中已经否定了正则图中如果有奇圈t 2 1 7 1 2 勘2 七+ 1