（应用数学专业论文）图的d（β）点可区别边染色及其概率方法.pdf

摘要 2 0 噼，张忠辅等人在【4 9 】提出了圈的d ( 卢) 一点可区别边染色的概念，本文通 过概率方法和具体构造染色的方法研究了d ( j 日) 一点可区别的边染色 本文有四部分构成 第一部分主要是引如一些在本文所需要的基本概念与预备知识 第二部分讨论了d ( 卢) 一点可区别边染色的性质，给出了路和圈的d ( 3 ) 一点可区 别边色数，并归纳总结r ，g ，& ，晶，l 】i 么的d ( p ) 一点可区别边色数 第三部分通过具体构造染色的方法讨论并给出了联图v r v r ，v r 的d ( p ) 一点可区别的边色数 第四部分通过具体构造染色的方法讨论并给出了p = 1 ，2 ，3 时五类冠图 r ，晶，g ，r ，的d ( 卢) 点可区别边色数 第五部分先应用l o v 矗s z 局部引理的一般形式，讨论并得到了对最大度为 d 的简单图g ，有也一硝( g ) 3 2 d 2 ，d 4 ，题一谢( g ) 8 d ，d 6 以及p 4 ，d 4 时，d ( p ) 一点可区别的边色数的上界即始一。d ( g ) 2 厄万= 面警然后，用得 到t d ( 2 ) 一点可区别的边色数的另一个上界，有1 6 2 i n 6 ，6 1 6 “砸，则 r 2 一谢( g ) + 1 + 、l n 关键词：l o v s z 局部引理；d ( 卢) 一点可区别边染色；d ( p ) 一点可区别边色数；联 图；冠图 a b s t r a c t i n2 0 0 6 ，z h a n gz h o n g f up r e s e n tan e wc o n c e p to ft h e d ( 3 ) - v e r t e x - d i s t i n g u i s h i n gp r o p e re d g e - c o l o r i n ga n dc o n j e c t u r e ，s e e 【8 】i nt h i sp a - p e r ，w eh a sb e e ns t u d i e dd ( f 1 ) - v e r t e x - d i s t i n g u i s h i n gp r o p e re d g e - c o l o r i n g b yp r o b a b i l i s t i ca n d 昏y i r l gc o l o r i n g so fag r a p h t h ep a p e rc o n s i s t so ff i v ep a r t i nt h ef i r s tp a r t ，w ei n t r o d u c es o m ef u n d a m e n t a lc o n c e p t st h a to f t e n u s e d i n t h e p a p e r i nt h es e c o n d p a r t ，w e d i s c u s st h e p r o p e r t i e s o f d ( f 1 ) - v e r t e x - d i s t i n g u i s h i n gp r o p e re d g e - c o l o r i n ga n d ，w eh a sb e e no b t a i n e d 磁一t ，d ( 晶) a n d 磁一耐( g ) ，b yi n d u c t i o nw eh a sg o t t e nt h ed ( 励一v e r t e x - d i s t i n g u i s h i n g p r o p e re d g e - c o l o r i n gc h r o m a t i cn u m b e ro fr ，& ，g ，r ， i nt h et h i r d p a r t ，w eh a v ed i s c u s s e da n do b t a i n e dt h ed ( 芦) 一v e r t e x - d i s t i n g u i s h i n gp r o p e re d g e - c o l o r i n gc h r o m a t i cn u m b e ro f vr vr ，如v rw i t hg i v i n gc o l o r i n go fag r a p h i nt h ef o u r t hp a r t ，w eh a v ed i s c u s s e da n do b t a i n e dt h ed ( f 1 ) 一v e r t e x - d i s t i n g u i s h i n gp r o p e re d g e - c o l o r i n gc h r o m a t i cn u m b e ro f r ， & ，g ，r ，w i t h g i v i n g c o l o r i n g o f a g r a p h ，w h e n p = l ，2 ，3 i nt h el a s tp a r t ，w i t ha p p l y i n gt h eg e n e r a lf o r mo ft h el o v s z zl o - c a ll e m m a ，w eh a v ed i s c u s s e da n do b t a i n e dt h a t 磁一以( g ) 3 2 d 2 ，d 4 ，磁一t ，d ( g ) 8 d ，d 6a n dw h e n 卢芝4 ，d 4 ，x 0 一砌( g ) 2 弱面掣f o ra n ys i m p l eg r a p hg w i t hm a x i m u md e g r e ed w eh a s g o t t e na n o t h e ru p p e rb o u n d sf o rd ( 2 ) 一v e r t e x - d i s t i n g u i s h i n gp r o p e re d g e - c o l o r i n gc h r o m a t i cn u m b e r ，x ，2 一谢( g ) a + 1 + i na f o rt h es i m p l e g r a p hw i t hm a x i m u md e g r e ea 1 6 2 i n6 ，m i n i m u md e g r e e ( f 1 6 、l n w i t ha p p l y i n gt h eg e n e r a lf o r mo ft h el o v 缸zl o c a ll e m m ab ya n o t h e r a b s t r a c t m e t h o d k e y w o r d s ：w i t ha p p l y i n gt h eg e n e r a lf o r mo f t h el o v d s zl o - c a l l e m m a ；d ( p ) 一v e r t e x - d i s t i n g u i s h i n gp r o p e re d g e - c o l o r i n g ，d ( p ) - v e r t e x - d i s t i n g u i s h i n gp r o p e re d g e - c o l o r i n gc h r o m a t i cn u m b e r ，g r o w ng r a p h ， 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包含为获得西北师范大学或其他教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意 签名：l 翌壶盂， 日期： 关于论文使用授权的说明 本人完全了解西北师范大学有关保留、 交论文的复印件，允许论文被查阅和借阅； 采用影印、缩印或其他复制手段保存论文。 签名：通壶盏 导师签名 使用学位论文的规定，即：学校有权保留送 学校可以公布论文的全部或部分内容，可以 ( 保密的论文在解密后应遵守此规定) 毛上 刖f j 图的染色问题是图论的主要研究内容之一染色的基本问题就是确定其各种染色法 的色数四色猜想首次在点染色中提出，从而使图论染色理论的研究工作得以发展之 后，许多数学工作者都致力于点染色，边染色 2 4 - 2 6 】的研究1 9 7 3 年，g r i i n b m u n 5 1 首次 提出了图的无圈点染色，a l o n 和j e m e n 等在【6 ，4 6 1 中对无圈边染色，无圈点染色作了 进一步的讨论1 9 9 3 年，b u r r i s 吲介绍并研究了点可区别的边染色( 或称强边染色，或 称o b s - 染色) ，s c h e i p ，e e 姐梦，h o r f i t k 和s o t g k 等在 2 8 - 3 6 】中作了更深入的研究，得到了 一些好的结果2 0 0 2 年，张忠辅朋首先提出了图的邻点可区别的边染色，( 或称邻强边 染色) 问题，掀起了图论染色问题研究的一股热潮，现在也已经得到很多有价值的成果 【1 1 1 3 ，1 3 7 - 4 0 1 2 0 0 8 年，张忠辅等人【4 9 】提l i l t 图的d ( p ) 一点可区别边染色的概念本文通 过概率方法和具体构造染色的方法研究了d ( 口) 一点可区别的边染色 因为对阶不小于3 ，且不含孤立边的图g 如t ，d ( g ) 存在并且有x q 。d ( g ) = 。( g ) ，x ，d “( g ) = x ，耐( g ) ，而邻点可区别的边染色与点可区别的边染色都有一 些好的性质，于是在本文的第二部分讨论了d ( 卢) 一点可区别边染色的性质，我们 把它们和f 4 9 1 中图的d ( 卢) 一点可区别边染色的两条性质总结在一起，从而便于以后 的研究，a c b u r r i s 在1 2 8 中给出了r ，g 的点可区别边色数，由于随着p 的增长， 求r ，g 的d ( j 臼) 一点可区别边色数难度也进一步加大，因而我们在本文的第二部分 仅给出p = 3 时，路和圈的d ( 3 ) 一点可区别边色数，然后归纳总结r ，g ，& ，厩，r ，h l 的d ( p ) 一点可区别边色数 在本文的第三部分，通过具体构造染色的方法讨论并给出了联图s 。vr vr ，kv r 的d ( 卢) 一点可区别的边色数 在本文的第四部分，通过具体构造染色的方法讨论并给出了，给出了卢= l ，2 ，3 时五类 冠图r ，岛，g ，最，的d ( 口) 一点可区别边色数 2 0 0 2 年国际数学家大会上n o g aa l o u 作了离散数学方法与挑战的一小时报告，图的 概率方法这个新颖，活跃的研究领域正受到国际数学界的普遍关注l o v g s z 局部引理，作 为概率方法中核心部分之一，是证明具有某些特定属性的目标的存在性的一个非常重要 的工具它的优点是我们只需证明具有某些特定属性的目标存在的概率值大于0 即可， 前言 即使这个概率值非常小相关应用参见文献【3 】，【4 l ， 1 0 - 1 4 ， 1 7 - 2 3 对于d ( 1 ) 一点可区别边染色( 邻点可区别的边染色) ，用概率方法( 或分析方法) 得到 了一些很好的结果b a l i s t e r ，g y i ；r i ，l e h e l 和s c h e l p 在文【1 1 l 中得到：若图g 没有孤立边， 则邻点可区别的边色数也sa + o o o gx ( o ) ) g h a n d e h a r i 和h a t a m i 在文1 1 2 】中得到： 若图g 是简单图，最大度 1 0 6 ，则邻点可区别的边色数毛( g ，1 ) + 2 7 、五i i 夏 h a t a m i 又在文1 1 3 】中得到：若图g 没有孤立边，最大度 1 泸，则邻点可区别的边 色数也+ 3 0 0 本文在第五部分先应用l o v a s z 局部引理的一般形式，讨论并得蓟 了对最大度为d 的简单图g ，有赔- v d ( g ) 3 2 d 2 ，d 4 ，赐一州( g ) 昭i ，d 6 以及卢 4 ，d 4 ，对d ( p ) 一点可区别的边色数的上界，即炻一o g ) 2 、瓦扩= 可学然后，用 另法得到t d ( 2 ) 一点可区别的边色数的另一个上界，有1 6 2 i n 6 ，6 1 6 、x i n a ，财 2 一耐( 研a + 1 + 、l n 在本文中所讨论的图均为有限图对于标准的图论记号可参看【1 】，【2 5 】， 1 7 】和【4 8 j 2 1 预备知识 在这一节中我们给出一些与本文相关的基本概念，原理和引理详细内容请参阅所 列文献 定义1 1 对图g 切，映射，：v ( a ) 一 l ，2 ，一，七) 满足对任意相邻的顶点 u ，口，有l ( u ) ，( 口) ，则称，是g 的一个卜正常点染色，简记作蠹一p v c ，且称 x ( g ) = m i n k l g 有扣正常点染色 为g 的点色效 1 】 对图g ( k e ) ，映射，：e ( g ) 一 l ，2 ，) 满足对任意相邻的边e 1 ，e 2 ，有l ( e 1 ) f ( e 2 ) ，则称，是g 的一个扣正常边染色，简记作k p e c ，且称( g ) = m i n k l g 有 如正常边染色为g 的边色数【l 】 定义1 2 对阶数不小于3 的连通图g ( k e ) ，设o 为正整数，令映射，：e o 1 ，2 ，o ，若v u ， y ( g ) ，1 d ( u ，口) p ，有c ( “) c ( v ) 则称，为g 的一个 o t d ( 国一点可区别的边染色，简记为n d ( 所一v d p e c ，对一个图进行a d ( 卢) 一 点可区别的边染色，所需的最少的颜色数称为图g 的d ( f 1 ) 一点可区别的边色数，记为 珏一t i d ( g ) 4 9 1 当p = 1 时，图的d ( 1 ) 一点可区别的边染色就是邻点可区别边染色，记x ，l 卅( g ) = 。( g ) ，当p = d i a m ( g ) ( d i a m ( g ) 指图的直径) 时，图的d ( f 1 ) - 点可区别的边染色就是 点可区别边染色x 钆( g ) = “( g ) 所谓图的两个点u ，口间的距离是指这两个点之间的最短路的长，用d ( u ，t ，) 表示 定义1 3 设图g 与圩是点和边都不相交的简单图，若v ( a v 胃) = v ( a ) u y ( 日) ， e ( g v h ) = e ( g ) u e ( h ) u i “e ( g ) ，v e ( h ) ，则称g v h 是g 与h 的联图每 两个顶点对应的边均不交的简单图g l ，g 2 ，g k ( m 3 ) 的联图g 1vg 2v vg 竹1 称为一个多重联图 定义1 4 阁将随机试验e 的所有可能结果组成的集合称为e 的样本空阿，记为 n ；n 的一个子集 称为事件；有限概率空问( q ，只) 是由一个有限的样本空间0 和 概率函数只：n f o ，1 1 ，满足以下几点：( 1 ) 只( z ) = 1 ；( 2 ) b ( a ) = 只( 。) ；( 3 ) # nz e 3 令五= n a ，则只( a ) = 1 一只( a ) ；( 4 ) p ( a u b ) = 只( ) + 只( 日) 一只n b ) ；( 5 ) l p ( a u n ) s 只( a ) + 只( 日) ，更一般地，只( ua ) b ( a ) ，称为概率的次可加性 - = - 1= l 定义1 5 埘对于n 的每个喾，有b ( z ) = 南，称为均匀分布；n 中的一个均匀元素 是一个随机元素，每个概率均是相等的 定义1 6 嘲如果事件a 发生的概率不受事件b 的影响，称事件a 对事件b 是独立 的；对n 个事件a l ，也，a ，着对v a ，如“j ， ，j = l ，2 ，砷有b ( a n 冉) = b ( a i ) 只( a j ) 成立，称事件a l ，如，厶两两独立；对n 个事件a l ，a 2 ，如，若对 l 事件的任意子集 a - ，如，a ，有b ( a l i n a ) = b ( a 1 ) ，称事件a i ，如，如互耜 i f f i 2 独立 定义1 7 埘令a l ，也，厶为概率空间的，1 个事件，对事件的集合s ，t 是s 中 一些事件( 或事件的补) 构成的任一子集，如果满足只( a ln ) = 只( a ) ，则称a f i t 与事件的集合s 互相独立；以v ( h ) = 1 ，2 ，t 1 ) 为顶点的有向图日= ( h ) ，e ( 日) ) 被称作相关图 = 争如果对所有 a ：1 isn ，a 与集合 鸟：( i ，j ) 岳e ( 日) ) 中的事 件互相独立 引理1 1 ”( 第一矩量原理) 如果e ( x ) t ，则只( x t ) 0 注：多应用于x 是正整数值且e ( x ) 0 引理1 2 4 1 ( 互相独立原理) 假设x = 墨，局，是独立随机试验的序列， 妒= a l ，如，a ) 是事件的集合，对每个a ，都存在忍x 每个a 被只决定，如 果尻n ( 乃。，玩) = 以那么a 与 a 。，如，如 互相独立 l o v d s z 局部引理主要用来证明具有某些特定属性的目标的存在性问题在实际遇到 的问题中，经常会出现事件之间相互依赖的情况，这时候，如果依赖的数量被充分地限制， 我们仍可断定成功的概率为正下面给出本文用到的l o v d s z 局部引理的一般形式，还有 其它形式参见1 4 】 引理1 3h ( 一般局部引理) 考虑( 典型的坏的) 事件的集合e = a i ，a 2 ，a 。) ，对每一个a ，都存在现 ( 协可以空) ，使得每一个a 与e 一( d i u a i ) 互相独立( 对某个b e ) 如果有实数 4 x l ，勋，x n l o ，1 ) 使得对每个l i n ，只( a ) 新1 7 ( 1 一) ，则中所有事件 “ a j e d i 都不发生的概率至少是i - ( i z 1 ) 0 = l 5 2 图的d ( f 1 ) - 点可区别的边色数及其 性质 圈的染色的基本问题就是确定其各种染色法的色数【“嚼为了解决网络权的分配问 题，b u r i i s ，b 踞g 阻等人先后提出点可区别边染色( 也称为强边染色) 【1 一2 0 0 2 年，张忠辅 等人提出了图的邻强边染色( 邻点可区别边染色) ，2 0 0 6 年，张忠辅等人提出了图的距离不 超过卢的任意两点可区别的边染色，即d ( 所点可区别的染色所谓图的两个点t ，口间的距 离是指这两个点之间的最短路的长，用d ( 牡，t ，) 表示 定义2 1 对阶数不小于3 的连通图g e ) ，设o p 为正整数，令映射，：e o 1 ，2 ，q ，若讹， y ( g ) ，1 d ( t ，口) p ，有c ( u ) c ( v ) 则称，为g 的一个 a d ( f 1 ) - 点可区别的边染色，简记为n d ( f 1 ) 一v d p e c ，对一个图进行n d ( 所一 点可区别的边染色，所需的最少的颜色数称为图g 的d ( p ) 一点可区别的边色数，记为 x 台一埘( g ) 1 4 9 】 引理2 1 对连通图g ，i v ( g ) l 3 ，x ，。( g ) x ，胁d ( g ) 州( g ) 对连通图g ，r i v ( g ) j 3 设啦表示使得任意两点间的距离不超过p 的度g 为 的点的最 大数目，且记即( g ) = m i n o i ( ：) 2 啦 【4 9 】 引理2 2 对连通图g ，j y ( g ) i 3 有 x ，卢州( g ) ，印( g ) 由于当卢= 1 时，图的d ( 1 ) 一点可区别的边染色就是邻点可区别边染色，当 p = d i a m ( g ) ( d i a m ( g ) 指图的直径) 时，图的d ( f 1 ) 一点可区j j f 的边染色就是点可区别边 染色，因此d ( p ) 一点可区别的边染色除了上述性质外，还有下面的性质： 引理2 3 矧设玩是n 3 的n 阶完全图，则p ( g ) x 0 ( g ) p ( g ) + 1 引理2 4 研老i d ( u ) = d ( v ) = ( g ) ，且缸口e ( g ) ，则) 幺( g ) + 1 6 2 图的d ( 卢) 一点可区别的边色数及其性质 下面讨论r ，c ；，& ，k 。，r ，- 的d ( p ) 一点可区别的边染色 p , , 拱 c j d ( f 1 ) 点可区别的边色数 由于求r 的d ( 卢) 一点可区别的边色数难度较大，对于p = 1 p = 筇= d 缸m ( g ) 时，a c b u r r i s ，r h s c h e l p ，张忠辅等人给出如下结论： 引理2 5m 设r ，n 3 ，有 妣，= 像篡 引理2 6 【删设r ，n 3 ，有 机c 驴像三： 引理2 7 【矧设r ，n 3 ，j 为满足g ) n 一2 的最小的整数，则 fj “j ；l ( m o d 2 ) h n = 学， 地( r ) = 鳓兰o ( m o d 2 ) j t n 学； lj ， 否则； 现在我们讨论p = 3 时的情况， 定理2 i 设r ，n 3 ，有 缸一耻雠薹 当时饥5 时，令r = 吨地一i ，是从e ( r ) 到 l ，2 ，3 ，4 的一个映射：用 色l ，2 ，3 ，4 循环的染边m t l 2 ，地均，一1 显然，是圈r 的一个4 - d ( 3 ) 一v d p e c - g 的d ) 一点可区别的边色敦 由于求g 的d ( p ) 一点可区别的边色数难度较大。对于p = 1 ，卢= 2 ，卢= d i a m ( a ) 时，a c b u r r i s ，r h s c h e l p ，张忠辅等人给出如下结论： 7 2 图的d ( f 1 ) 一点可区别的边色数及其性质 也) = 3 , n = - o ( m o d 3 ) ；卧5 ； b 三 证明 当n = 3 ，4 ，5 时，结论显然 n ，n = 3 ，4 ，5 ； 5 ，n ；o ( m o d 5 ) 5 ，n 0 ( r o o d 5 ) 当n 6 时，r n ；o ( m d d 5 ) 时，令g = 口1 吨，口l ，f 是从e ( g ) 到 l ，2 ，3 ，4 ，5 ) 的 一个映射：用色1 ，2 ，3 ，4 ，5 循环的染边m t j 2 ，l j 2 均，一l ，v v 1 显然，是圈g 的一 个5 - d ( 3 ) - v d p e c 当时1 1 , 6 ，且n 0 ( r o o d s ) 时，分为四种情况： 情况1 ，ii1 ( m 汹) ，对边q t j 2 ，v 2 v 3 ，v n 一2 一l 循环地染颜色1 ，2 ，3 ，4 ，5 然后对 边 l 染颜色3 情况2ni2 ( r o o d 5 ) ，对边口l v 2 ，v z v 3 ，一3 一2 循环地染颜色1 ，2 ，3 ，4 ，5 然后对 边一2 v n - l iv n v l 染颜色2 ，4 8 ，l_l_，、i-ll = g - 宝 有 始 文 一 扎g 殴 2互理定 2 图的d ( p ) 一点可区别的边色数及其性质 情况3n 毫3 ( r o o d 5 ) ，对边口l t ) 2 ，t b 地，一4 一3 循环地染颜色l ，2 ，3 ，4 ，5 然后对 边一3 一2 ，2 一l ，”l 染颜色2 ，3 ，4 情况4 佗毫4 ( r o o d 5 ) ，对边v , v 2 ，v 2 v 3 ，一5 一4 循环地染颜色l ，2 ，3 ，4 ，5 然后对 边一- 3 ，v n 一3 v n - 2 , t n 一2 l p n - l ，t ，l ，染颜色1 ，2 ，3 ，4 上面得到的圈的染色显然为它的5 _ d ( 3 ) v d p e c 综上所述结论得证 & 的d ( 卢) 一点可区别的边色教 引鹰2 1 1 册设叉，n 2 ，有 也( 岛) ： 2 一= 2 ； 【n 3 ； 引理2 1 2 2 7 1 设& ，n 2 ，有 x 0 ( & ) = f t 由于& 是直径为2 的图因此 x 0 ( & ) = 璐一“( & ) = n 2 ) j 0 的d ( p ) 一点可区别的边色数 引理2 1 3 【矧对完全图k 。伽3 ) ，有 如( 纸) ： l ，幢o ( m 0 弛) 【t l ，n 兰1 ( r o o d2 ) 由于纸是直径为1 的图因此 比( ) = x 0 埘( ) = n 1 ) f n 的d ( p ) 一点可区别的边色致 引理2 1 4 【7 】设r ，n 2 ，有 x 0 ( r ) = 引理2 1 5 【柚】对扇r ( i y ( r ) l = n + 1 ) ，有 “( r ) ； 1 归2 3 i t l ， ，l24 9 2 3 3 = = 一 n n n 3 4 n ，_l-，、iil【 2 图的d ( 芦) 一点可区别的边色数及其性质 由于r 是直径为2 的图，因此 x 0 ( r ) = 殇一“( r ) = n 伊2 ) 1 的d ( f 1 ) - 点可区别的边色数 引理2 1 6 对轮矸0 ( i y ( h i ) i = n + 1 ) ，有 儿( ) ： 5 归3 ； l n ，n 4 引理2 1 7 对轮h 0 ( i y ( n 0 ) i _ n + 1 ) ，有 ( ) ： 5 ”3 ； 【协n 4 f h 于彤。是直径为2 的图，因此 】( 0 ( w ；) = 而一埘( - ) = n ( p 2 ) 1 0 3 两类联图的d ( p ) 一点可区别边染色 本章我们给出多重联图岛vrv 尸n 的d ( 卢) 一点可区别边染色，联图v r 的d ( 所一点可区别边染色 由于联图是直径为2 的图，它的d ( 卢) 点可区别边染色卢2 就是点可区别边染色，因 此研究联图的d ( p ) 一点可区别的染色，只需研究联图的d ( 1 ) 一点可区别边染色( 邻点可区别 边染色) ，点可区别边染色 3 i 关于一类多重联图s kvr vp n f 纂j d ( f 1 ) 一点可区别边染色 本节我们给出多重联图s kvr vr 的d ) 一点可区别的染色 a m = o ，i ，2 ，一，m ) ，颤= 1 ，2 ，一，m 记 y ( ) = 啦扣= 0 ，i ，m ) ，e ( s m ) = u o u d i = i ，2 ，m 一条路 y ( r ) = q d = 1 ，2 ，n ，e ( r ) = t 。码+ 1 b = i ，2 ，t l l 另一条路 y ( r ) = 嘶i p = l ，2 ，n ，e ( r ) = t 屿件l i p = i ，2 ，f l , 一1 ) 引理3 1 ( v r v r ) = f r l + 2 n x 乙c v b v 只，= 兰+ 。，三三耋 3 两类联图的d ( f 1 ) 一点可区别边染色 嘲乜，萎 3 两类联图的d ) 一点可区别边染色 ，( 仇地) = + 5 ( i = 0 ，1 ，2 ) ；，( 地t ) = l + 6 ( m o d7 ) “= 0 ，1 ，2 ) ； ，( t | 0 啦) = i ( i = 1 ，2 ) ；f ( w l t 0 2 ) = 7 ；f ( v l t l 2 ) = 4 对此，有 o ( u o ) = ( 7 ) ；口扣1 ) = f 2 ，3 ；0 ( t 1 2 ) = ( 3 ，4 ) ； o ( v 1 ) = 3 ) ；e ( 也) = 5 ，；0 ( 叫i ) = 6 ；e ( t 也) = t 1 所以，是岛v 马v p 2 的一个7 - a s e c 情况3 当m 3 时，由引理3 ，为了证明结论成立只需给出s k vbv 忍的一个，l + 5 - a s e c 为此，令，为： f ( w l v j ) = j d = 1 ，2 ) ；f ( w l u , ) = i + n 0 e a 。) ； f ( u 堙v j ) = j + 1 0 = 1 ，2 ) ；f ( w 2 u 1 ) = i + 4 ( i a m ) ； ，( l t ) = + 6 0 a m 1 ) ；，( m t b 。) = 3 ； ，( 地仉) = i + 7 ( m o d 仇+ 5 ) ，i a 。一l ；f ( v 2 u 。) = 4 ； ，( t 0 蛳) = 0 = 1 ，2 ) ；，( t 0 蜥) = 8 ；f ( u o u , ) = l + 5 ( i = 4 ，5 ，m 1 ) ；i ( u o u 。) = 5 ； ，( 啦啦) = 5 ；，( 叫i 蚴) = m + 5 对此，有 o ( w 1 ) = m + 4 ) ；0 ( w 2 ) = l ；0 ( - ) = 4 ；o ( 忱) = 6 ) ； c ( t e 0 ) = m + 5 ) ；e ( 。) = a + 3 ，i + 4 ，i + 6 ，l + 7 ，i ，( i = l ，2 ) ；c ( u 3 ) = 6 ，7 ，8 ，9 ，l o ； c ( m ) = + 七：3 七7 ( r o o dm + 5 ) ( 4si m 1 ) ；g ( “m ) = m + 3 ，m + 4 ，3 ，4 ，5 1 所以，是v b v p 2 的一个m + , 5 - a s e c 综合上述三种情况定理3 2 为真 乜，三 1 3 3 两类联图的d ( p ) 一点可区别边染色 f ( “o u l ) = 8 ；，( 咖) = j o = 1 ，2 ，3 ) ；，( t l o t 咋) = p + 3 0 , = 1 ，2 ，3 ) ； ，( 饥) = j + l o = l ，2 ，3 ) ；，( u 1 p ) = p + 4 0 , = l ，2 ，3 ) ； f ( v l 唧) = p + 5 ( p = 1 ，2 ，3 ) ；，( t j 2 札j ，) = p + 6 ( m d d8 ) 0 = 1 ，2 ，3 ) ； ，( 均唧) = i + 7 ( m o d8 ) “= 1 ，2 ，3 ) ；i ( v i v j + 1 ) = j + 3 0 = 1 ，2 ) ；，( t 1 ) = p + 1 0 = 1 ，2 ) ； 对此，有 e ( t l o ) = 7 ；o ( u 1 ) = l ；0 ( 口1 ) = 3 ，5 ) ；d ( 协) = 6 ) ；0 ( 蜥) = 6 ，7 ) ； o ( w 1 ) = l ，3 ；0 ( 地) = 4 ) ；d ( 蚴) = 4 ，5 ) 所以，是两v b v b 的一个8 - a s e c 情况2 当m = 2 时，由引理3 ，为了证明结论成立只需给出昆vb vb 一个9 - a s i c 令，为： i ( w l 吩) = j u = 1 ，2 ，3 ) ；i ( w l u ) = i + 4 ( i = 0 ，1 ，2 ) ； f ( w 2 码) = j + l ( j = 1 ，2 ，3 ) ；，( t 啦“i ) = i + 5 ( i = 0 ，1 ，力； ，( 缸b 吩) = j + 2 u = 1 ，2 ，3 ) ；f ( w 3 u , ) = i + 6 ( i = 0 ，1 ，2 ) ； ，( 口l t i ) = i + 7 a = 0 ，1 ，2 ) ；，( 吨挑) = i + 8 ( m o d9 ) 0 = 0 ，1 ，2 ) ； f ( v 3 蛳) = 9 + i ( m o d9 ) 0 = 0 ，1 ，2 ) ； f ( u o 1 ) = 2 ；i ( t 0 u 2 ) = 3 ；i ( w l w 2 ) = 9 ；i ( w 2 w 3 ) = l ；f ( v i v 2 ) = 5 ；i ( v 2 v 3 ) = 7 对此，有 0 ( t l ，1 ) = 7 ，8 ；0 ( t ，2 ) = 8 ) ；o ( w 3 ) = 9 ，2 ； o ( 1 ) = 4 ，6 ；d ( 吨) = ( 6 ；0 ( t j 3 ) = 6 ，8 ； o ( ) = 1 ) ；0 ( u t ) = 3 ，4 ；口( 抛) = 4 ，5 所以，是岛v 尼v b 的一个9 - a s e c 情况3 当m 3 时，由引理3 。为了证明结论成立只需给出s m v b v 恳一个m + 7 - a s e c 为此，定义，为： f ( w l 吻) = j o = l ，2 ，3 ) ；f ( w l u l ) = i + 4 ( i a 。) ； i ( w 2 v j ) = j + 1 0 = 1 ，2 ，3 ) ；，( t 也饥) = i + 5 ( i 4 ，) ； f ( w 3 v i ) = j + 2 0 = 1 ，2 ，3 ) ；i ( w 3 u i ) = i + 6 ( i a m ) ； ，( 口1 t i ) = i + r ( i 4 。) ；，( 啦“i ) = i + 8 ( m o dm + 7 ) o a 。) ； 1 4 勰v ，= i 麓m + 2 n ，, = n m + l ； 3 两类联图的d ( 口) 一点可区别边染色 l ( , , j w p ) = p + j o a ：，p a ：一2 ) ；，( 吩t 一1 ) = n 一1 + j 0 心一1 ) ； ，( 一1 ) = 2 n + l ；，( 码) = 2 n + j + l ( j 心一2 ) ；，一1 w n ) = 1 ；，( ) = 2 n - 1 ； ，( 吩+ 1 ) = j o a 二一1 ) ；，( t 唧郇+ 1 ) = 2 n + p 一1 ；p a ：一2 ；，( 。一l l l j n ) = 2 n 显然，是v r v 岛的一个m + 2 n - a s f _ e 情况2 2 当n m 时，令，为： ，( 嘶吩) = p + j l ( p a ：，j 以) ；i ( w p t o ) = p + ，l 细a ：) ； ，( 缸p t i ) = p + n + l ( p ；i a 二) ；，( 啦t 1 0 ) = j + 2 n u a ：) ； ，( 吩地) = j + i + 2 n ( m o dm + 2 n ) 0 代一l ； a ：l 1 ) ，( t ) = 3 n + i + 1 ( m o dm + 2 n ) ( i a t 一2 ) ；，( 。一1 ) = 2 n ；，( 吩t 。) = j + n o a ：一1 ) ； ，u m ) = l + 2 n ；，( 蛳t 1 1 ) - 3 n + i ( m o dm + 2 n ) ( i 镌) ；f ( v j v ，+ 1 ) = 2 n + j - 3 ( j 群一1 ) ； ，( l t k ) = m + 2 n ；，( t 蜘+ 1 ) = p 一1 ( p = 2 ，n 1 ) 显然，是v r v r 的一个m + 2 n - a $ e c ， 情况3 当m = 1 ，n 4 时，为了证明结论成立只需给出且v r v r 一个2 + 2 n - a s e c 令，为： f ( t o u l ) = 2 + 2 n ；f ( u o v , ) = j o a ：) ；f ( u o w p ) = p + n ( p ：) ； l ( u l v ，) = 1 + j ( j a ：) ；i o , 1 w p ) = 1 + p + n ( p a ：) ； ，( t ) = n + p + + 1 ( m o d2 + 2 t 1 ) 加a ：，j 二) ； ，( 吩吩+ 1 ) = j + 3 u e a ：一1 ) ；，( 札i p 叫“1 ) = p + 2 p 霹一1 ) 显然，是岛v r v r 的一个2 + 2 n a s i y , c 综合上述三种情况可知，定理3 4 为真 综合定理3 1 一定理3 4 ，可得： 一 定理3 5 对任意的正整数仇，乱，有 叫撩i i ：2 ； 3 两类联图的d ( 3 ) 一点可区别边染色 s m v r v r 的点可区别边色数 比c v 最v 只，= 至+ 。，三三耋 证明 分三种情况考虑： 情况1 当n = 1 ，m = 1 ，& v p t v p x = k 4 ，由引理1 知结论为真 情况2 当n = 1 ，m = 2 ，有 弘( 岛v 只v r ) = m 舣 m i n 训( 3 ) ，m 瞰n g ) 2 ) ) = = 5 ， 为了证明结论成立只需给出岛vp 1 v 只的一个5 一v d e c 令，为： ，( t | 0 t 1 ) = 1 ；，( t 0 撕) = 2 ；，( t 1 0 口i ) = 3 ；f ( u o w l ) = 4 ； f ( u l l ? 1 ) = 2 ；f ( u x w t ) = 3 ；，( t 2 1 ) = 4 ；f ( u 2 w 1 ) = 1 ；f ( v l 伽1 ) = 5 对，有： e ( t l o ) = 1 ，2 ，3 ，4 ，；c ( u t ) = l ，2 ，3 ；e ( 地) = l ，2 ，4 ) ；c ( v i ) = 2 ，3 ，4 ，5 ；c ( w 1 ) = f 1 ，3 ，4 ，5 ) 所以，是s 2 v r vp l 一个5 一v d e c 情况3 当m 3 ，有： p ( 品v b v p 1 ) = m a x m i n a i ( m ：。) s ，m i n a i ( ；) 2 m ，) = m + s ， 为了证明结论成立只需给出s k v p l v 只的一个m + 3 一v d e c 令，： f ( u o u , ) = i ，i a ：；，( t i 川1 ) = m + l ；f ( u o w , ) = 7 7 1 + 2 ； ，( 甜i “t ) = + l ，i a 二一l ；f ( w t u , ) = i + 2 ，l a ：l l ；，( t ，l 仇) = m + 2 ；，( t m 硼1 ) 害 l ；，0 1 t ，1 ) = m + 3 对，有： c ( t o ) = l ，2 ，m + 2 ) ；c ( t l ) = l ， + 1 ，i + 2 ，i a ：一l ；c ( t ，n ) = m ，m + 2 ，1 ) ；o ( v 1 ) = l ；o ( w t ) = 2 所以，是v r vp l 的一个m + 3 一v d e c 综合上述三种情况定理3 6 为真 1 7 定理3 7 若m 1 ，t l ；2 ，则 i7 m = 1 ； x 0 ( & v b v b ) = 7 ， m = 2 ； 【m + 5 ，m 3 证明 分三种情况考虑： 情况l 当l = 2 ，m = l ，最v b v 岛= k ，由引理1 知结论为真 情况2 当n = 2 ，m = 2 ，有： p ( 岛v b v b ) = 删峨 m i n n i g ) 5 ，m i n a i ( ：) 2 ) = 7 ， 为了证明结论成立只需给出岛v b