（运筹学与控制论专业论文）图的距离2着色的若干问题.pdf

摘要 图的距离2 着色来自所谓的频道分配问题：某一区域有若干电台，不同的电台要使用无 线电波发送信号，为了避免相互干扰，位置十分接近的电台要使用相差足够远的频道，位置 较近的电台要使用有一定相差的频道将频道分配给电台，目标是在保证电台互不干扰的前 提下使用最少的频道资源图g 的l 0 ，女) 一标号着色是图的l c 2 ，1 ) ，标号着色的推广，它是一个从 点集y ( g ) 到非负整数集的函数，满足条件：( 1 ) 当u v e ( g ) 时，l ，( “) 一，( 口) i 芝j ：( 2 ) 当d ( u ，”) = 2 时，l ( u ) 一，0 ) l2 图g 的l ( j ， ) 一标号数定义为：，k c a ) = m i n ! m a x f ( v ) ： y ( g ) ) ，即 图g 的所有l o ，女) 一标号着色的最大标号的最小值g 的一个”p u ，) 一圆标号着色是这样的一个 函数，：v ( a ) 一 o ，1 ，2 ，m 1 ) 且满足：当“和口相邻时，i ( u ) 一，扣) l 。j ；当u 和 距离 为2 时，i f ( u ) 一，( ”) k ，这里：。= m i n h ，m h ) g 所拥有的m - ( j ，) 圆标号着色中 的最小的m 称之为g 的一 k 数，记之为k ( g ) 在第二章中，我们在完全图的c 砒i a n 积的k k - 数的已有研究的基础上，进一步研究征 明了当n m 2 l r n 2 m 4 时，如果j 肛m ，那么b ( 蜀。k mx j q ) = ( n m 1 ) ；如 果j k m ，那么，( 懿j 硒) = ( n 一1 ) j + ( m 一1 ) k 当n m l g n = 2 m 4 时，如 果i l ksm 一1 ，那么k ( j 厶蜀。硒) = ( m l - 1 ) b 如果j k m - 1 ，那么，t ( j “x k r a x k l ) ( 佗一1 ) 0 + k ) + ( m 一1 ) k 当m n m za n d ，l 2 m 4 ，w es h o w ，量( 硒) = ( 肌一1 ) k i f j ks t ，l ，a n d t h a t ，( k n k m 硒) = ( n 一1 ) j + ( l 一1 ) k i f j k m f o r t l t n l a n d n ；2 m 4 ，w e s h o w ，蠹( x k m x k i ) = ( n r n 一1 ) k i f j l k f ，l 一1 ，a n d t h a t ，k ( k n x k m x k l ) s ( n 一1 ) 0 + 七) + ( m 一1 ) k i f j k m - 1 w e a l s o i n v e s t i g a t e k 女( j “k m j n ) w h e n m t l 0 ，图的标号着色( l d ( 2 ，1 ) 一 l a b e l i n g ) 是一个非负函数，：，( g ) 一【o ，o o ) ，满足条件： ( 1 ) l ，( ) 一，( 口) i 2 d ，若e ( g ) ； ( 2 ) i f ( u ) 一，( 口) 1 2 凼若d ( u ，口) = 2 若，是图g 的一个l d ( 2 ，1 ) 一l a b e l i n g ，我们就称，岛( 2 ，1 ) ( g ) 每个点在，下的象称为该点 的标号定义i i f c g ) l i = m q f ( v ) ：口y ( g ) ) ，则图g 的标号着色数( l d ( 2 ，1 ) 一l a b e l i n gn u m b e r ) 定义为：a ( g ，d ) = m i n ti i f ( c ) 1 1 1 奎童奎童堡圭兰垒丝塞 2 上述定义可用频道分配的语言来描述，其中g 中的点表示电台，如果两个电台十分接 近，则在g 中代表这两个电台的点u ，”相邻：如果两个电台比较接近，则d “口) = 2 在所有的 点口上指定值，扣) ( 代表电台使用的频道) ，根据定义这就保证了各电台之间不会相互干扰我 们的目标就是在所有满足条件的频道分配中，寻求使用频道资源最少的分配 r o b e m 提出的这一数学模型清楚地描述了频道分配问题的约束和目标，而g r i g g s 和y e h 提 出的k ( 2 ，1 ) - l a b e l i n g 标号着色更有一般意义由于这里的着色使用了实数的概念，和以往 图的整数值点着色有较大区别。给我们研究该问题增加了不少困难和麻烦g r i g 鲫y e h 很 好的解决了这个问题他们在【2 1 中给出了下面两个引理，将实数值标号着色l d ( 2 ，1 ) - l a b e l i n g 和r d _ 吼b 提出的整数值标号着色l ( 2 ，1 ) 1 a 岫l j n g 建立了联系 引理1 1 1 旧雾，掣20 ，d 0 ，七z + ，如果悻一圳k d , 那么l 一一l ，i k d , 其 唧一= i x d i d , = b f d i d 引理1 1 2 l 匀对任意的实教正 ( g ，d ) = d a ( g ，1 ) 由这两个引理，对于任意的实数d 0 ，如果函数，满足约束( 1 ) 和( 2 ) ，那么任意”y ( g ) ， 取厂扣) = l f ( v ) d j d ，也满足约束( 1 ) 和( 2 ) ：如果x ( a ，d ) = l i f l i ，其中，l d ( 2 ，1 ) ( g ) ，那么存 在g 的一个整数值的工l ( 2 ，1 ) 一l a b e l i n g 函数，满足f = dx ， 所以有下面的定理： 定理1 1 3 1 霸对于任意的图g ，存在一个整数值的l t ( 2 ，1 ) 一l a b e l i n g 函& f ：v ( g ) 一 o ，1 ，2 ， 使得l i ，( g ) h = a ( g 1 ) 从而，关于图“( 2 ，1 ) 0 曲e f i 叼问题的研究就只需考虑d = 1 的情形为了简便，我们 将l 1 ( 2 ，1 ) - l a b e l i n o 简记作l ( 2 ，1 ) - l a b e d i n g 对于一个给定的图g ，它的l ( 2 ，1 ) - l a b e t i n g ( l ( 2 ，1 ) - 标号着色) 是定义在y ( g ) 上的非负整数函数，满足条件：( 1 ) 若w e ( g ) ，i l ( u ) 一，( ”) l 2 ；( 2 ) 若d ( “，口) = 2 ，i f ( u ) 一，( 口) l 1 相应的我们将工1 ( 2 ，1 ) ( g ) 记作l ( 2 ，1 ) ( g ) ， ( g ，1 ) 记 作 ( g ) k - l ( 2 ，1 ) 枞i n g 表示最大标号不大子女的l ( 2 ，1 ) - l a b e l i n g g r i g 挚和y e h 提出和研究了更一般的l ( m l ，f ，1 2 ，m ) - 标号着色，其中，满足条件：对1 isn ，若d ( ，f ) = i ，i ，扛) 一，( f ) i 盹，其中是正整数，m l 她2 m r o 是给 定的正整数如果n = m l = 1 ，那么，就是正常的点着色如果n = 2 ，m l = j ，1 2 = 女，则，就 是工u 蚪标号着色 图的工( 2 ，1 ) 标号着色和l ( 1 ，1 ) 标号着色曾在在过去十几年里得到了广泛研究，并且有 了很多结果工伉i ) 标号着色和工似1 ) - 标号着色也有一些相关结果 图g 的一个一d 砂圆标号着色是这样的一个函数f ：v ( g ) 一 o ，l ，2 ，m 一1 r 满 足：当t 和”相邻时，l ，( 一f ( v ) l 。j ；当u 和”距离为2 时，l f ( u ) 一，( 口) k 七，这里：蚓m = m i ，m 一纠) g 所拥有的”n 0 ，) 圆标号着色中的最小的m 称之为g 的q ，女一数，记之为勺 ( g ) 这一概念由i i e u v e l ，l e e s e 和s h e p h e r d1 19 】首先提出并研究 1 2 关于标号着色已有的基本结果 在频道分配问题的现实背景下，标号着色这一概念的提出并得到广泛研究无疑具有实 际意义最近十几年很多人进行了相关的研究，也得出了一些重要的结果 定理1 2 1 l 訇对任意的图g ，a ( g ) + 1 定理1 2 2 阎令r 为包含n 个顶点的路更l 】a ( 马) = 2 ，a ( 忍) = 3 ， ( 只) = 3 ，a ( r ) = 4 ，v ，l 5 定理1 2 3 【訇令g 为包含n 个顶点的圈则有a ( g ) = 4 定理1 2 t 4 【訇若t 是最大度1 的树，则a ( 习= + l 或+ 2 定理1 2 5 【匀若图g 的最大度为，则 ( g ) 2 + 2 a c h a n g 和g u o 对这个结果做了改进，得到下面的定理： 定理1 2 6 【嗣若图g 的最大度为，则 ( g ) 2 + a g r i g g s ：和y e h 对一般图做了如下猜想： 猜想1 2 7 i 霸对任意最大度2 的图g a ( g ) 2 对几类特殊的图诸如弦图、直径为二的图等，这个猜想被证明是正确的但对于一般的 图，此猜想仍未得到证实 定理1 2 8 曲对任意图g ，例：g 一定有这样的一个k k 一标号着色，且其每个标号都可以表 示成形式：町+ 卢砖p 砂：对任意正整数c ：c k k ( g ) = b 砖( g ) 定理1 2 9 旧若g 是最大度为的弦图，则a ( g ) ( a + 3 ) 2 4 这个上界在【6 】里被改进到了【( + 3 ) 2 4 j 一1 定理1 2 1 0 3 对奇强弦图( o d ds t r o n g l yc h o r d a lg r a p h o s f - c h o r d a l ) g ，a ( g ) 2 a 定理1 2 1 1 【q 对度为的鼬g i l l a r t i l i n g g ，h 1 ( g ) = + 掣一2 ，其中d = 0 ，1 ，2 定理1 2 1 2 1 8 对n 一方体吼，a ( q k ) 2 n 除上述结果外，对积图( p r o d u c t g r a p h ) 诸如路积图、路圈积图、圈积图，p r a n a v a k j h a 等 已做了研究【2 7 】一1 ，我们将在第二章中给出相关的结果外平面l 圈( o u t e r p l a n a rg r a p h ) ，平面 图，直径为2 的图，排列图( p e r m u t a t i o n g r a p h ) ，分裂图( s p f i t g r a p h ) 等也都有人进行t l ( 2 ，1 ) - 标号着色研究，得到了相应的界关t l ( d ，1 ) 一标号着色问题研究，其难度无疑比l ( 2 ，1 ) 标号 着色问题着色要大很多下面是有关l ( d ，1 ) ，标号着色的一些基本结果： 奎查奎兰堡圭耋堡篁塞 定理1 2 1 3 i 功对任何最大度为的图g ，知( g ) a 2 + ( d 一1 ) a 定理1 2 1 4 【j 功对任何最大度为的树t ，a + d 一1 k ( t ) s m i n a + 2 d 一2 ，2 a + d 一2 ) 定理1 2 1 5 口功若g 是最大度为的弦图( c h o r d a l g r a p h ) ，则k ( g ) s ( 2 d + 一1 ) 2 4 定理1 2 1 6 口功若g 是最大度为的奇强弦图( o d ds t r o n g l yc h o r d a lg r a p h o g f - d l o r d a l ) ， 则知( g ) d a 定理1 2 1 7 1 4 令r 为包含n 个顶点的路，则有知( 恳) = d ，a d ( p 3 ) ；d + 1 ，a d ( p 4 ) = d + 2 ，知( 昂) = d + 2 ，v t l 5 定理1 2 1 8 1 4 1 令g 为包含n 个顶点的圈则有 id + 2 若4 i d ， 知( g ) = d + 3 若4 t d 2 id ， i 2 d 若2 十d 此外g e o r g e sj p 和m a n r od w 等对l u ，”l a b e l i n g 做了较多研究，他们给出了完全 图积图和树等特殊图类的工o ，砂标号着色数，或确定，女一数或确定 一数的界【1 1 】_ 【1 3 | ，当 然也有许多待解决的问题。在讨论过的图类中，乘积图是一类很有趣的图类，它是通过图 运算构造出的图类。许多有趣的无线网络只有一些简单的因子比如路、圈。如出维网格就 是d 条路的c a r t e s i a n 积，出维环面就是d 个圈的c a r t e s i a n 积。因此，路、圈、完全图等一些特殊 图的c a r t e s i a n 积被优先考虑。目前，两条路的c a r t e s b n 积、两个圈的c a r t e s i a n 积、两个完全 图的c a r t e s i a n 积已有一些结果，其中主要讨论了它们的沁，1 数，晶【8 l ，c kx ，i m l 2 5 】 2 8 】， g c 【3 0 】的沁，1 一数已基本确定，j o j 岛的k 数已完全确定【2 4 】。三个图的c a r t e s i a n 积目前 结果不多，三个相同的完全图的c a r t e s i a n 积砀的a i 一数，只有n 为奇时被确定，n 为 偶时，只给出了上界1 1 1 | o 对于9 女一数，目前，路、树、圈及完全图的c 棚i a n 积的o 数有 讨论，在c a r t e s i a n 积中，只有两个完全图的c a r t e s i a n 积已确定【2 3 】。 l c j ，) 标号着色相对于l ( d ，1 ) - 标号着色在研究中给我们又增加了些许困难很多图类 即使我们得到了工( 2 ，1 ) 标号着色数，也很难得至l j l ( d ，1 ) 一标号着色数或缸) 标号着色数过 去十几年中，l ( 2 ，1 ) 一标号着色的研究相对来说已经比较丰富l ( d ，1 ) 一标号着色和工0 ，) 标号 着色的研究还有很多空缺之处，其原因主要在于问题的难度加深了但是，由于 k a u k j ，l ( g ) = k l i k j , k ( g ) 知，( g ) k r i i l , ( g ) = f j 阍，1 ( g ) 如果知道了图g 的l ( 矗1 ) 一标号着色数，我们便知道t g 的l ( j ，女) 一标号着色数的上下界，易于 进一步研究图g 的l o ，”标号着色数 奎塑奎兰堡圭兰堡垒塞 5 1 3 本文的主要工作 本文主要研究三个完全图的c 凹峨i 8 n 积的上 ) 标号着色问题，同时探讨了连通度为的 图g 的k 数与其子图g s 的各个连通分支补图的路覆盖数之间的关系，这里s 是g 的一个缸顶 点割 在第二章中，我们在完全图的c 吼郎i a n 积的a f f 数的已有研究的基础上，进一步研究 证明了当n 争m l r n 2 m 4 时，如果，肚m ，那么，t ( 厩j 硒) = ( 口一1 ) 女；如 果，肚m ，那么k ( j 矗x j 硒) = 一1 ) j t - ( m 一1 ) 当 m t r n = 2 m 4 时，如 果j ksm - 1 ，那么 ( j o j r 。硒) = ( n m 一1 ) b 如果j 肚m 一1 ，那么如，k ( k x k , x k t ) ( n 一1 ) 0 + ) + ( m 一1 ) 女当m n m l 且t l 2 m 4 时，如果j k 曼i n ，则，女( 墨。函) = ( m l 一1 ) k 如果j k m ，则，k ( j o 硒) = m 一1 ) j + ( m 一1 ) 当t l m f 且n = 2 m 4 时，如果j k m 一1 ，则k k ( j 厶 k m j q ) = ( n m 一1 ) 女；如果i l k ，l 一1 ，则，( k 矗硷) ( n 一1 ) 0 + ) + ( m 一1 ) 我们也对m n 2 m 时的x j , k ( 。x 玛) 做了一些研究 另外，在本章及下一章中，除非特别说明，j 、n 、m 和f 都是正整数，且满足n m z 2 及j k 2 1 完全图的c a r t e s i a n 积与相关结果 图g 与日的c a r t e s i a n c 昭, g h 指的是顶点集y g v ( g h ) = v ( g ) v ( h ) ，边集为e ( g h ) = ( z ，p ) ，( 一，矿) ：z = 一且e ( 日) ，或者口= l f ，且z 一e ( g ) ) 的图g 表示k 个 图g 的c a r t e s i a n 积，例如磅= ，砩= 珞，其中为n 个顶点的完全图。 设n 和b 是两个正整数且n 一1 ，则k ( k ：) = ( ，l 一1 + ( 2 n 一2 ) 躬 ( f i ) ：若j k n 一1 ，则k k ( k ：) = ( n 2 1 ) 另外，他们借助c a y l e y 图的方法，得到了p 为素数时蝣的乜，1 一数 在【2 1 】中，g e o r g 和m a u r o 研究了砩的k 一数 定理2 1 3 1 2 当j k 5 2 嗣 ，q 3 岂磁的，k 墩是却；当j 肛5 2 时，q 3 兰磁的h k 一 熵+ 5 k 定理2 1 4 1 2 j 1 设，l 是奇数，且n 3 ， ( i ) 若j 3 n 一4 ，则k k ( 砩) = m 一1 ) u + 3 女) ； ( i i ) j 勃s n 一2 ，则k ( k i ) = ( n 2 1 ) ； ( n i ) 若n 一2 j k 3 n 一4 ，月q ，( 磋) 茎( ，i 一1 ) 0 + 3 的 定理2 1 5 籼设n 是偶数， ( i ) 若j 肛n 2 ，则k ( 碟) = ( 铲一l i ( f 产+ 2 n ) k ，h i 2 j 女n 一2 ， ( i i ) k i ( ：) n o + 3 女) ， n 一2 2 n ( n 一2 ) 在 2 2 】中，n 3 个完全图的c a r t i 积玩的，一数也已经完全确定，这里t 1 ，t 2 ，k 互 素，且2 t l t 2 k 在接下来的几节里，我们主要研究3 个完全图的c a r t e s i a n 积k m 硒的k 女一数 2 2 扎= m f 在【2 1 】中，j 矗凰的，数已被研究。本节中，我们考虑n = m 耐的3 个完全图 的c 吼i 积的k k 一数 我们知道，如果h 是g 的子图，那么a ( 日) s ( g ) 【匈根据定理2 1 2 ，定理2 1 4 和定理2 1 5 ， 我们有下面两个定理 定理2 2 1 设t l 是奇数且n 3 ， ( i ) j k n 一2 ，则，k ( 玩k 。硒) = ( n 2 一1 ) ； 东南大学硕士学位论文 8 ( i i ) 若，3 n 一4 ，则，k ( x 硒) = ( t l 一1 ) 0 + 3 女) ； ( i i i ) 若t l 一2 j k 3 n 一4 ，则，k ( k n 局) s ( ，l x ) 0 + 3 k ) 定理2 2 2 设n 是偶数， ( i ) 若j n 2 ，则，( x 硒) = ( 舻一1 ) 拓 ( i i ) 若n 2 j k 曼t l 一2 ，则b ，k ( k jx ”硒) ( n 2 + 2 n ) k ； ( i i i ) 若n 一2 2 n ( n 一2 ) ，则，k ( 玩硷) s ( n 一1 + n ( 2 n 一1 ) 下面，我们考虑n 是奇数的一般情形首先给出这样几个概念。我们称顶点”= ( o ，b ，c ) 矿( k m 硒) 为k n k m 硒中的第n 行，第b 列和第c 层的顶点设h 给定：0 h m 一1 ， 对于第0 层上的顶点，我们称集合d h = ( o ，b ，0 ) l ( b 一m o d m ) r o o d m = h 中的顶点为第0 层 上的第h 条对角线上的顶点 设，是从y ( j 厶x 硒) 映到 o ，1 ，2 ，舻一1 ) 上的函数，其定义如下： ，( ( n ，b ，o ) ) = 【! ! 笋卫6 一( ，l 一1 ) a lm o d n 2 ； ，( ( 口，b ，c ) ) = ，( ( ( d + c ) m o d 竹，( 6 + c ) m o d m o ) ) ，喜e 中：0 c l 一1 由，的定义和模代数性质，可以得到下列关于函数，的性质： ( 0 1 ) ：，( ( 啦( b + 2 ) m o d n ，o ) ) = 【，( ( 口，6 ，o ) ) 一n m o d n 2 ； ( 0 2 ) ：如果o n 一1 ，那a f ( ( ( a + 1 ) m o a n ，6 ，o ) ) = 【，( ( o ，b ，o ) ) 一m 一1 ) l m o a n 2 ； ( 0 3 ) ：由上两个性质，如果d l 和n 是奇数，且当2 是奇数时，3 f s n + 1 ；当f 是偶数时，3 f s 一2 如果j 肛n 一1 ，那么，k ( x x 硒) = ( n 一1 ) u + 2 k ) 证明：对j 肛n 一1 ，有。i ( j 0 x j 靠硒) ，k ( 砩) = 一1 ) 0 + 2 k ) 故我们只 要证k 女( j 厶j 毛x 甄) ( ( n 一1 ) 0 + 熬) ，下面我们只要构造甄x 蚝垃的一个跨度 为一1 ) 0 + 2 ) 的缸) 标号着色 设l 是从y ( j 0 j 矗硒) 到非负整数集上的映射，其定义为：工( ( 口，b ，c ) ) = 巧+ ( r + t ) k ， 当且仅当，( ( d ，b ，c ) ) = r n + t ，其中o t ，r s t l 一1 易见，工的跨度是( n 1 ) o + 2 k ) 从而我 们只要去证明上是甄凰局的一个缸”标号着色 设口l 和v 2 是j 0 垃中的两个顶点，且，p 1 ) = r l n + t 2 ，池) = r 2 ”+ t 2 ，其 中1 o l ，t 2 n 一1 不妨设，h ) ， ) 由引理2 2 4 ，有( r 2 n + t 2 ) 一( 1 n + t 1 ) n l 从而 当”1 和吨相邻，我们有 工( 啦) 一l ( v 1 ) = ( r 酊+ ( r 2 + t 2 ) k ) 一( r l j + ( r l + t 1 ) k ) = ( r 2 一r 1 ) j + ( r 2 一r 1 ) k + ( 赴一t 1 ) k ( r 2 一q b + ( 再- 再弦一融一i 一( 如一r i ) n l 女 = ( r 2 一r 1 ) j 一( r 2 一r l 一1 ) ( n x ) k j 类似地，由引理2 2 3 ，有( r 2 n + t 2 ) 一( r t n + t 1 ) 1 从而当口l 和睨距离为2 时，我们有 l ( 啦) 一l ( v 1 ) = ( r 0 + ( r 2 + 屯) k ) 一( r 0 + ( n + t 1 ) k ) = ( r 2 一r 1 ) j + ( r 2 一r 1 ) k + ( t 2 一t 1 ) 女 ( r 2 一r 1 ) j + ( r 2 一r 1 ) k + 【1 一( r 2 一r 1 ) n k = ( r 2 一r 1 ) j 一( r 2 7 1 ) ( n x ) k + k k 奎查奎耋堡圭耋堡丝茎 1 1 2 3 ，l 2 m 在本节中，我们将考虑n 2 m 时的3 个完全 的c a r t e s i a n 积的 数首先我们定义一 个从y ( xk m 硒) 到 o ，1 ，2 ，m l 上的映射 对，l m ，设t o = m i n 1 s t ，；m 一1 i2 t m o d 仃= o ，t m o d t ，l = o ) ，t z ，可以推断，一 定存在两个正整数p 和q ，使得2 t o = p n ，t o = q m 易见，t o 墨意舞，如i 嚣舞设n m = r o t o 由o 的定义，容易得到下列性质 ( 0 1 ) ：如果南是偶数，那么p = 焉希，q = 昂赫，r o = 2 ( n ，m ) ，t 0 2 菥知； ( 0 2 ) ：如果叠焉是奇数，那么p = 杀，口= 南，r o 兰，m ) ，t o = 焉 由上面的性质，不难得到( 1 ) 当t l 2 m 时，有口 p ，t o m ；( 2 ) 当侣= 2 m 时，有q = p ，r 0 = 2 ( n ，m ) = 2 m ，t o = 互存渤= m = 量；( 3 ) 当m n m 设g 是从y ( j 0 k m 硒) 到 o ，1 ，2 ，l m 一1 ) 上的映射，且其定义如下： g ( ( ( 2 t + r ) m o d n ，t m o d m ，o ) ) = r t o + t ，0 t s t o 一1 ，0 r r 0 一l ； g ( ( o ，b ，c ) ) = g ( ( ( d + c ) m o d n ，( b + c ) r o o d m ，o ) ) 其中0 sc s z 一1 玺堕奎堂堡圭耋堡篁奎 1 2 下两个矩阵，给出了目f l k l 5 凰k l 在映射g 下的第0 层和第1 层的顶点标号 03 77 4 1 5 5 28 9 3 06 1 84 5 8 2 2 3 6 0 13 8 7 5 1 6 5 3 2 43 1 6 8 9 4 68 3 5 46 123 9 7 61 7 8 4 2 53 2 6 91 0 4 7 1 8 5 5 6 234 07 7 4 88 52 6 3 3 7 01 1 7 81 9 5 6 6 344 1 1 24 98 6 2 73 47 1 4 27 9 2 0 5 76 45 7 2 1 3 5 0 8 7 2 83 5 6 4 38 09 15 8 6 5 3 6 7 31 4 5 1 8 8 2 9 74 4 8 1 2 2 5 9 a 第。层的顶点标号 6 784 58 22 33 0 13 8 7 5 1 6 5 36 0 3 1 6 89 4 68 32 4 6 123 9 7 61 75 4 2 5 3 2 6 91 04 78 4 5 5 6 234 07 7 1 8 8 5 2 6 3 37 01 14 8 1 9 5 6 6 344 17 8 4 9 8 6 2 73 47 11 2 7 92 05 76 4 54 2 1 3 5 08 72 83 5 7 2 4 3 2 15 86 5 6 7 3 1 4 5 18 82 93 6 74 48 1 2 2 5 96 6 3 7 7 4 1 5 5 2 8 90 b 第1 层的项点标号 接下来，我们将证明，当n 2 r a 时，g 是k l 的一个l ( m ，1 ) 一标号着色 引理2 3 1 设n m l ，如果 1 = ( 口l ，6 l ，c 1 ) 和圪= 她，6 2 ，c 2 ) 是y ( k m 硒) 中距离为2 的顶点，那么9 ( v 1 ) g ( t 1 2 ) 证明：当c l = 吃= o 时，我们有g ( ”1 ) 9 池) 下面我们设c 1 0o r 吃0 假设9 ( v 1 ) = 9 ( t j 2 ) ，那么9 ( ( ( o l + c 1 ) m o d n ，( 6 l + c t ) r o o d m ，o ) ) = g ( ( ( 0 2 + c 2 ) i n o d n ，( 6 2 + 吃) m o d m ，0 ) ) 由c = o 时g 的定义，可推得( 口l + c 1 ) m o d n = ( 0 , 2 + c 2 ) m o d n ，吼+ c 1 ) r o o d m = 池+ c 2 ) r o o d m 由 于( o l ，h ，c 1 ) 和( 眈，6 2 ，c 2 ) 有一个分量相等，从而可推得他们的另外两个分量必须相等，这与 他们是距离为2 的顶点矛盾，得证口 引理2 3 2 设n 2 m ，如果整数i ，s 满j 己二0 i n m 一1 ，1 川m l ，且0 i + s 幻m ，这与1 1 8 i m - - 1 另；盾， 奎查奎兰堡圭耋丝篁塞 1 3 从而i r r s i 1 又因为p n 一1 = 2 ( 幻一i ) 2 1 t t 。i = l z n 一( r r a ) i k i n i r r s i 忙h i ， 所以我们有蚓 m ，如果整孰，s 满足：0 i m l 一1 ，1sh m 一1 ，且o i + s m 一1 ，那么在第喉上，i + s 与i 对应顶点必不同列 证明：设 = r t o + t ，t + 8 = r a t o + t s 用反证法假设i + s 与i 对应顶点必在第0 层的某一 列上，那么必存在一个整数z ，使得t t s = 霉m 又因为q m 1 t o 1 l t t a i = m ，所以 我们有圳 2 m 4 ，如果整数 ，8 满足0 i = r t o + t 墨n m 一1 ，1 墨m 一1 ， $ - 0 i + 8 = n t o + t s n m 一1 ，那么一定不存在这样的整数z 【1 ，l 一1 】【l ，m l 】，使得 ( 2 t + + 加”d “2c 2 t e + 咖删“，( 2 1 ) 【o + = ) m o dm = t 。m o d m 。 证明：h j 及证糕1 发设存在整数z 【1 ，f 一1 】【1 ，竹l 一1 1 ，便得 j ，协+ r + = ) r o o d n = ( 2 t ，+ r s ) m o d m l ( t + ：) r o o d m = 如m 。d m 则必存在整数z 与”，使得 。2 t + + ；r ：+ “z 一= ，2 。t s ，+ “一m 号 z = x n - 2 y m + ( r - r s ) , 一， 下面我们对r 一“= 0 ，1 ，一1 分别讨论 当i r n i = o 时，有 。z一=。x。n：-一2。y。m+,扪。 ( 2 2 ) ( 2 3 ) ( 2 4 ) 奎查奎童堡圭耋堡丝圣 1 4 因为2 i l ，m x l , 所以。= z n 一2 1 t m 【l ，m 一1 1 号2 m + 1 孤曼胁+ 1 ) m - 1 ，a h 此- - i 推得若 0 对，我们有0 且，一1 否则，若口= 0 ，则有l m 一1 ；若f = - 1 ，则 有一( 2 m 一1 ) 一( m + 1 ) ，这都与n 2 m 和$ 是整数矛盾进而我们有 1 8 l ：i t - t 8 i 帅+ 1 m 驴0 ( 2 5 ) i 一白+ 1 ) m + 1 m ，” 0 及t t ， 0 故由z = z n 一2 9 m 一1 【1 ，m 一1 j ，我们有2 y m + 2 s s ( 2 y + 1 ) m 又因为t t ，= 一z n + 妒n + 1 t o 一1 ，所以妒l = 幻一册+ 可m + 2 芝一0 + 1 ) m + 2 ，由 此可得”一口如果y = 一q ，那么- p n + 2 = 一2 如+ 2 m 一2 t o + m = 一册+ m ，这与 是整数及n 2 m m 矛盾。故y 一g 从而有1 8 i = 5 = 幻一o 一“) = t o + $ n 一咿一1 _ - 2 如+ 2 y m + 2 一可m 一1 = t o + 妒7 l + 1 = ( g + 剪) m + 1 m 这也与l i s i m l 勇；盾 当r r i = 1 时，有 ”“- 2 y m “， ( 2 7 ) 【t t l = 一x n + ”m 一1 又易见s 2 m 如果口1 = ( d l ，h ，c 1 ) 和t j 2 = ( 眈，6 2 ，吃) 是y ( 厶坼。垃) 中相 邻的两个顶点，那么1 9 h ) 一9 ( 圪) i m 由引理2 3 1 和引理2 3 5 ，结合b ，标定着色的代数性质，我们有 定理2 3 6 如果n 2 m 4 ，j k m ，那么 知女( k m 硒) = ( m l 1 ) k 对n 2 m ，酗肛2 m 3 ，有 定理2 3 7 如果n 2 m 4 屈j k m 3 ，那, k k ( j “k m 硒) = ( n 一1 ) j + ( m 一1 ) k 证明：由定理2 1 1 ，当j 肚m 时，有，( j 矗玛。硒) k k ( j k 蜀。) = m l h + ( m - 1 ) k 从而只要证，k ( x 蜀。硒) n 1 ) j + ( m 一1 ) 进而我i f j r 要构造j “x k t 的一个跨度为m 1 ) j + ( m 一1 ) 的0 ，砂标号着色 设l 是从y ( 蜀。k z ) 到非负整数集的映射，且其定义为l ( ( n ，6 ，c ) ) = r j + t k ，当且仅 当9 ( ( o ，b ，c ) ) = r m + t ，其中o t m 一1 ，0 r n 一1 易见l 的跨度为机一l h + ( m 一1 ) 女类 似定理2 2 6 的证明，可证l 是j kx 墨。硒的一个女) 一标号着色口 2 4 礼= 2 m 本节中，我们考虑n = 2 m 时的3 个完全图的c a r t i a j l 积j & 蜀。硒的，p 数 首先，我们证明n = 2 m 时，上一节中定义的映射g 是玩k m 硒一个工( m 一1 ，1 ) 一标号 着色 引理2 4 1 设n = 2 m 4 ，如果整数i ，。满足；0 i = 响+ t n m 一1 ，1 茎h m 一2 ， 且o i + s = r s t o + g r i m - 1 ，那么一定不存在这样的整数z 【1 ，l 一1 】【1 ，m 一1 1 ，使得 ( 2 汁? 托) 删”协一曲删 ( 2 8 ) io - 4 - ：) m o d m = 屯m o d m 。 证明：用反证法假设存在一个整数z f 1 ，z 一1 1 【1 ，m 1 1 ，使得 j ( 2 t + r + z ) m o d n = ( 2 如+ b ) m o d n ， 【( t + 。) m o d m = t s m o d m 则必存在整数z 和，使得 。2 t + + 。r ：+ “z 一= 妒2 t m s + r l 一辛z = x n - 2 y m + ( r - r , ) , 一如， 由于l r r s i 1 ，下面我们分别讨论