（应用数学专业论文）几类图的泛宽度染色和p1全标号.pdf

山东师范大学硕士学位论文 几类图的泛宽度染色和( p ，1 ) 一全标号 刘秀丽 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 随着图论理论的发展，图论分出许多分支起源于1 5 0 年前的四色猜想的染色 问题有着极其重要的地位，并且在组合分析和实际生活中有着广泛的应用染色 问题是图论研究中一个很活跃的课题，得到了许多有趣而实用的结果，同时又拓 展出一些新的分支近年来，又提出了许多新的染色问题，这些染色问题在频率分 配中有很强的应用，如：泛宽度染色，0 ，1 ) 一全标号 定义1 【1 】设g = ( y ( g ) ，e ( g ) ) ，d 是一个正整数，x 是v ( g ) 的一个子集如， 果x 中任意两个顶点的距离都大子d ，称x 是一个宽度箱，d 叫做x 的宽度 显然，d 一宽度箱也是( d 一1 ) - 宽度箱、( d 一2 ) 一宽度箱等等 定义2 【1 】给定图g = ( y ( g ) ，e ( g ) ) ，使得v ( a ) = x l u 拖u u x k ( x i ( i = 1 ，2 ，k ) 是v ( g ) 的宽度两两不同的宽度箱) 的最小整数k ，这个整数k 叫做 图g 的泛宽度色数，记做洳( g ) 图g 的一个大小为x p ( g ) 的染色叫做洳( g ) 一 染色显然，此处我们的目的是最小化k 可以假设对每个i ，托是个i 一宽度箱 图的泛宽度染色是一种以距离为依据准则的图顶点的剖分问题对于不具有特 定图结构的任意图来说，研究图的泛宽度色数是非常困难的，而且目前已知的结 论中，也都是针对具有具体图结构的图类来研究的，如：无限正方形【2 】，完全图 的剖分图s ( k n ) 1 1 的泛宽度色数，无限3 正则树的泛宽度色数是7 【3 1 因此， 在文献【1 】中作者猜想：确定任意图的泛宽度色数是n p 完备问题 在频率分配问题中，会有下面的情形出现：我们需要给中转站分配频率波段( 每 个中转站得到对应于一个整数的频率波段) 为了避免干扰，如果两个站点离得非 常近，那么它们的频率之差至少要相差2 ，而且，如果两个站点离得近( 不是非常 山东师范大学硕士学位论文 i a ) ，那么它们得到的频率不同受到这个问题的启发，g r i n g g s 和w e h 4 引进 了工( 2 ，1 ) - 标号，它的自然推广是l ( p ，1 ) - 标号 定义3 【5 】设p 是一个非负整数，图g 的一个i ( p ，1 ) 一标号是从v ( a ) 到一个整 数集合的映射l ，必须满足：对于任意的顶点u ， ( 1 ) 若如( “，t ，) = 1 ，则f l ( u ) 一三( 口) f p ； ( 2 ) 若d a ( u ，口) = 2 ，贝0j l ( u ) 一l ( 秒) l 1 特别地， w h i t t l e s e y 等人在文献【7 】中研究了g 的剖分图岛( g ) 的三1 ) 一标 号，g 的剖分图s 1 ( g ) 是有图g 在每条边上插入一个点所得到的图研( g ) 的 三0 ，1 ) 一标号对应与g 的l ( p ，1 ) 一全标号 定义4 【5 】设p 是一个非负整数，图g 的一个k 一，1 ) 一全标号是一个映射 ，：v ( g ) u e ( g ) 一 o ，1 ，2 ，后) ，使得： ( 1 ) a 的任意两个相邻的顶点u 和口，有i ，( u ) 一，( u ) i 1 ， ( 2 ) a 的任意两条相邻的边e 和e ，有i f ( e ) 一( e ，) | 1 ， ( 3 ) a 的任意两个相关联的点口和边e ，有i ，( 口) 一，( e ) i p ， p ，1 ) 一全标号的跨度是指两个标号差的最大值，图g 的，1 ) 一全标号的最小跨度 叫图g 的( p ，1 ) 一全标号数，记做a 孑( g ) 5 1 f r e d d i eh a v e t 和m i n - l iy u 给出了巧( g ) 的上下界，提出了0 ，1 ) - 全标号猜 想：，谬( g ) ( g ) + 2 p i 在本文中，我们主要得到如下结论： 定义2 1 【3 8 】设g 表示任意一个连通图，其中v ( a ) = 勘l ，钞2 ，v n ) ，g 7 表示 g 的一个复制图，其中v ( a ) = 钍1 ，u 2 ，u n ) 在g 和g 7 之间加匹配v i u i ( i = 1 ，2 ，n ) ，得到新图d ( g ) ，则 y ( d ( g ) ) = v ( a ) uv ( a 7 ) ，e ( d ( g ) ) = e ( g ) ue ( g 7 ) u v i u i ，i = 1 ，2 ，n ) ，不 妨称d ( g ) 为双图。 2 山东师范大学硕士学位论文 定理2 1 设r 表示一条阶为n 的路，则当他 5 时，有x p ( r ) ) = 5 定理2 2 设i v 表示一个轮，有洳( d ( ) ) = 礼+ 2 定义3 1 1 设g 和g ，表示任意两个连通图，其顶点集分别为： v ( g ) = “l ，乱2 ，) 和y ( g ，) = v l ，v 2 ，) ， 在g 和g ，之间叠加匹配u i v i ，u i v i + 1 ，u i ? 3 i + 2 ，u i v i + m ，u i v i + ( n 1 ) ( i = 1 ，2 ，n ； 仇= 0 ，1 ，2 ，n 一1 ；当i + m 礼时，i + m 为模n 意义下的加法) 这样得到一系 列图g 瓣，g 瓣，g 翳，g 瓣称为图g 和g ，的弱联图显然g 瓣= g v g 定理3 1 1 设p n 表示一条阶为仃的路，有a ；( 硝m + 1 ) = a + 2 = m + 5 ( m = 0 ，1 ，2 ，竹一2 ，n 4 ) 定理3 1 2 设g 表示一个圈，有入；( 醴梦1 ) a + 2 = m + 5 ( m = 0 ，l ，2 ，n 一 1 ) ；当n 为偶数时，a ；( 西1 ) = a + 2 = m + 5 ( m = 0 ，1 ，2 ，礼一1 ) 定义3 2 1 f 2 9 】设g 是一个简单图，v ( c ) = v 1 ，v 2 ，) 已是两个点的独 立集，g 阮】是通过j 1 2 代替g 的每个顶点后所得到的图，即g 的每个顶点v i 都有 一个复制点t ，厶中每个点仍按对应点的连边方式与其他点连边g 阮】的点集 和边集对应如下： y ( g 尼】) = v ( g ) u 口i ，呓，如】， e ( g 1 2 ) = e ( g ) u _ ( u ：u ：， ：i 口i e ( g ) ) ， 则称g 忆】为g 的点分裂图 定理3 2 1r 表示阶为礼的路，r 【如】表示路r 的点分裂图，则有 墩眦胪陡i ，4 定理3 2 2g 3 ) 表示一个圈，g 阮】表示圈g 的点分裂图，则当n 为偶 3 山东师范大学硕士学位论文 数时，有a 多( g 】) = 6 定理3 2 3 【如】表示完全图的点分裂图，则有a 多( 【如】) 2 n 定义3 3 1 【1 2 】设t ( g ) 表示任意图g 的全图，其顶点集对应于图g 的顶点和 边，全图t ( g ) 中两个顶点是相邻的，当且仅当图g 中对应的顶点或边相邻，或 者是对应的顶点和边是相关联的不妨设图g 的顶点集v ( g ) = u 1 ，v 2 ，口住) ， e ( g ) = e 1 ，e 2 ，e m ) ，那么 y ( t ( g ) ) = v l ，v 2 ，】u ( j i 饥吩g ) ， e ( t ( g ) ) = 【耽i 仇吻g u e i e ，l e 和勺在g 中相邻) u 仇勺i 忱和勺在g 中相 关联 定理3 3 1 设t ( g ) 表示圈g 的全图，则有a ；口( g ) ) 6 ；特别地，当n 为偶数时，有入手汀( g ) ) = 6 定理3 3 2r 表示阶为铊的路，? ( 蜀) 表示路r 的全图，则有 硪隅胪雌主 定理3 4 1 设g 表示一棵最大度( g ) = 3 的树，并且g 中所有的最大度点在 一条路上，则有 a ；( g ) 5 如表示阶为m + 1 的扇，当露个扇如的扇心连成圈时，用q 砖7 】表示设 y ( c k ) = v l ， v 2 ，u n ) ， y ( g 晶) = y ( 瓯) u “巧i t = 1 ，2 ，n ；j = 1 ，2 ，m ， e ( g f m ) = e ( g ) u v i u i j i i = 1 ，2 ，n ；j = 1 ，2 ，仇) u u t 3 u i j + l l i = 1 ，2 ，n ；j = 1 ，2 ，m 一1 ) 则对于图g f m 的( 2 ，1 ) 一全标号有下面的定理 4 山东师范大学硕士学位论文 定理3 4 2 当珏三o ( m o d 2 ) 时，有 墩仅吲= h 3 夏 在含有n 个顶点的路r 上，当且仅当两点的距离( 模) 为k 时加一条边，所得 到的图称为磁图【2 1 】【3 9 1 下面我们给出了部分磁图的( 2 ，1 ) 一全标号 定理3 4 3 对图磁，有a 2 t r 。k ) = 6 ，k 1 ，n 3 k + 2 在含有n 个顶点的圈g 上，当且仅当两点的距离( 模) 为k 时加一条边，所得 到的图称为c 尝图 2 2 1 下面我们给出了图c ( 仇1 ) 的( 2 ，1 ) 一全标号 定理3 4 。4a 多( c 乙) = 6 ，m 1 对于完全图k n ，钍，口y ( ) ，删去边删，其它点和边不变，则得到了图 一u u ，下面我们给出了一类图一u 口的( 2 ，1 ) 一全标号 定理3 4 5 当n 为奇数且n 3 时，有a 多( 一让口) = n + 1 不妨设y ( g ) = 勘1 ，v 2 ，) ，y ( g ) 的一个复制v 7 ( g ) 记为t 仳1 ，乱2 ，钆。 l ， 在y ( g ) 和其复制v 7 ( g ) 之间叠加不同的匹配，就构成了一系列新图：铲，卵，m ( c n ) 下面我们给出了这些图的p ，1 ) 一全标号 在y ( g ) 和v 7 ( g ) 之间叠加匹配u i v i ( i = 1 ，2 ，礼) 和讹饥+ 1 ( i = 1 ，2 ，佗一 1 ) ，u n v l ，得到图铲，有： 定理3 5 1 当n 为偶数时，有a 多( s n ) = a + p = p + 4 在铲( n 为偶数) 中，把酽中所有( t = 1 ，2 ，n ) 按u l u 2 ，? 比2 u 3 ，u n - - 1 u n ，u n u l 的方式连成圈，得到图卵，有： 5 山东师范大学硕士学位论文 定理3 5 2 当礼为偶数时，有a 外t 。1 n ) = + p = p + 4 我们称由m y c i e l s k i 作图法得到的图为m y c i e l s k i 图，记为m ( g ) a 1 1 给定图 g ，顶点集v ( v ) = 【口l ，u 2 ，) ，则图m ( g ) 的顶点集和边集分别是： y ( 掰( 固) = y ( u i g ，i = 1 ，2 ，死_ u 1 【叫 留gg ) ， e ( m ( g ) ) = e ( g ) u 仇弓i 仇g ，i ，歹= l ，2 ，佗) u ( w l i = 1 ，2 ，n ；v i g ，wg g 定理3 5 3 当佗为偶数时，有n + p 一1 = a + p - 1 a t ( m ( c n ) ) a + p + 2 = 船+ p + 2 关键词：泛宽度染色；泛宽度色数； 图；分裂图；全图；g f m 图；p 2 图； 6 分类号： 0 1 5 7 5 如，1 ) 一全标号；( p ，1 ) 一全标号数；弱联 磷图；m y c i e l s k i 图； 山东师范大学硕士学位论文 t h ep a c k i n gc o l o r i n ga n d ( p ，1 ) 一t o t a ll a b e l l i n go fs o m eg r a p h s l i ux i u u s h a n d o n gn o r m a lu n i v e r s i t y , j i n a n ，s h a n d o n g ，2 5 0 0 1 4 p e o p l e sr e p u b l i co fc h i n a a b s t r a c t n o wt h e r ea r em a n yf i e l d s 嬲t h ed e v e l o p m e n to ft h eg r a p ht h e o r y c o l o r i n gp r o b - l e m ，w h i c hc o m e sf r o mt h ef o u r - c o l o rc o n j e c t u r e ，p l a y sa ni m p o r t a n tp a r t c o l o r i n g p r o b l e mi se x t e n s i v e l ya p p l i e dt oc o m b i n a t o r i a la n a l y s i sa n dr e a l i s t i c sl i f e c o l o r i n g p r o b l e m i sv e r ya c t i v e ，s o m ei n t e r e s t i n gr e s u l t sa n dn e wf i e l d sa r eo b t a i n e d r e c e n t l y s o m en e wc o l o r i n gp r o b l e m sw h i c hp l a ya n i m p o r t a n tr o l ei nt h ef r e q u e n c ya s s i g n - m e n tp r o b l e ma r ep r o p o s e d ，s u c ha 8t h ep a c k i n gc o l o r i n ga n d ，1 ) 一t o t a ll a b e l l i n g 0 fg d e f i n i t i o n1 【1 】l e tg = ( y ( g ) ，e ( g ) ) b eag r a p h ，di sap o s i t i v ei n t e g e ra n dx i sab i p a r t i t es e t i ff o ra n y 仳，秽y ( g ) ，t h e r ei sd ( u ，v ) d , t h e nxi sc a l l e dap a c k i n g ，di sc a l l e dw i d t ho fx ad - p a c k i n g i sa ( d 1 ) - p a c k i n ga n da ( d 一2 ) 一p a c k i n ge t c d e f i n i t i o n2 【1 】l e tg = ( y ( g ) ，e ( g ) ) b eag r a p h ，a n d v ( a ) = x u 恐u u 甄， w h e r et h ep a c k i n g s 咒( i = 1 ，2 ，k ) a r ed i f f e n tw i d t h s ，a n dki st h em i n i m u m i n t e g e ro ft h ep a c k i n g s 五w i t hp a i r w i s ed i f f e r e n tw i d t h s ，七i sc a l l e dt h ep a c k i n g c h r o m a t i cn u m b e ro fg r a p hga n dw ed e n o t ei tw i t h ) ( p ( g ) ap a c k i n gc o l o r i n go f go fs i z e 硒( g ) i sc a l l e da 场( g ) 一c o l o r i n g o b v i o u s l y , t h eo b j e c t i v ei st om i n i m i z e 忌，w ec a na s s u m et h a tx i sa n - p a c k i n gf o re a c hi t h ep a c k i n gc o l o r i n gb a s e do nt h ed i s t a n c eb e t w e e nt h ev e r t i c e si sap a r i t i o n o ft h ev e r t e xs e t i ti sv e r yd i f f i c u l tt od e t e r m i n et h ep a c k i n gc h r o m a t i cn u m - b e ri ft h es t r u c t u r eo fg r a p hi sn o td e t e r m i n e d a n dt h ek n o w nc o n c l u s i o n sa r ea l l 7 山东师范大学硕士学位论文 a b o u tg r a p h so fs p e c i a ls t r u c t u r e s ，s u c ha st h ep a c k i n gc h r o m a t i cn u m b e ro fi r d i n i t es p u a r e e a n dt h es u b d i v i s i o ng r a p hs ( ) o fc o m p l e t eg r a p h 砖】，t h ei n f i n i t e 3 - r e g u l a rt r e eh a sp a c k i n gc h r o m a t i cn u m b e r7 1 3 t h e r e f o r e ，i nt h el i t e r a t u r e 1 ，t h e a u t h o rs u s p e c t e dt h a tt od e t e r m i n et h ep a c k i n gc h r o m a t i cn u m b e ro fa n yg r a p hi s n p - c o m p l e t ep r o b l e m i nt h ef r e q u e n c yo fd i s t r i b u t i o n ，t h e r ew i l lb eac a s ei nt h ef o l l o w i n g ：w en e e d t og i v eat r a n s i tp o i n tf o rt h ea l l o c a t i o no ff r e q u e n c yb a n d s ( e a c ht r a n s i tp o i n tc o r - r e s p o n d i n gt oa ni n t e g e rh a saf r e q u e n c yb a n d ) i no r d e rt oa v o i di n t e r f e r e n c e ，i f t h et w os i t e sa l ef r o mv e r yn e a r ，t h e nd i f f e r e n c eb e t w e e nt h ef r e q u e n c yo ft h e i r d i f f e r e n c e si sa tl e a s t2 ，t h e nt h e yh a v ed i f f e r e n tf r e q u e n c i e s i n s p i r e db yt h i sq u e s - t i o n ，g r i g g sa n dy e h 4 i n t r o d u c e dl ( 2 ，1 ) 一l a b e l l i n g s i t sn a t u r a lg e n e r a l i z a t i o ni s l ( p ，1 ) - l a b e l l i n g d e f i n i t i o n3 1 5 a nl ( p ，1 ) 一l a b e l l i n go fag r a p hi sa na s s i g n m e n tlf r o mt h e v e r t e xs e tv ( a ) t ot h ei n t e g e rs e ts u c ht h a t ：f o ra n y 铭，秒v ( a ) ( 1 ) l l ( u ) 一l p ) l p ，i fd a ( u ，u ) = l ； ( 2 ) l l ( u ) 一l p ) i 1 , i fd a ( u ，v ) = 2 w h i t t l e s e ye ta 1 i nt h el i t e r a t u r e 7 s t u d i e dl ( 2 ，1 ) - l a b e l l i n g so ff i r s ts u b d i - v i s i o ns ( g ) o fag r a p hg t h ef i r s ts u b d i v i s i o no fag r a p hgi st h eg r a p h & ( g ) o b t a i n e df r o mgb yi n s e r t i n go n ev e r t e xa l o n ge a c he d g eo fg a nl ( p ，1 ) - l a b e l l i n g o fs i ( g ) c o r r e s p o n d st oa nl ( p ，1 ) - t o t a ll a b e l l i n go fg d e f i n i t i o n4 i s ak 一( p ，1 ) - t o t a ll a b e l l i n go fgi sa na s s i g n m e n tff r o mt h e s e tv ( a ) u e ( g ) t ot h ei n t e g e rs e t o ，1 ，2 ，砖，s u c ht h a t ： ( 1 ) l ( u ) 一f ( v ) i 1f o ra n yt w oa d j a c e n tv e r t i c e su ，v y ( g ) ； ( 2 ) l f ( e ) 一f ( e ，) | 1f o ra n yt w oa d j a c e n te d g e se ，e e ( g ) ； ( 3 ) l f ( u ) 一厂( e ) l pf o ri n c i d e n tv e r t e xu v ( c ) a n de d g ee e ( g ) t h es p a no fa ( p ，1 ) - t o t a ll a b e l l i n gi st h em a x i m u md i f f e r e n c eb e t w e e nt w ol a b c l s t h em i n i m u ms p a no fa ( p ，1 ) - t o t a ll a b e l l i n go fgi sc a l l e dt h e ( p ，1 ) 一t o t a ln u m b e r a n dd e n o t e db y 碍( g ) 8 山东师范大学硕士学位论文 5 t h et r i v i a l i t yl o w e ra n du p p e rb o u n d sa r eg i v e nb yf r 4 d 6 i ch a v e ta n dm i n l i y ua n dt h e0 ，1 ) 一t o t a ll a b e l l i n gc o n j e c t u r e ：a t ( g ) a ( g ) + 2 p 一1 w eb r i e f l ys u m m e r i z eo u rm a i nr e s u l t sa sf o l l o w i n g ： d e f i n i t i o n2 1 3 s l e tgb eac o n n e c t e dg r a p h ，w i t hv ( g ) = v l ，v 2 ，仃n ) l e tg 7b eac o p yo f gw i t hy ( g ，) = u i ，呓，吒) an e wg r a p hd ( g ) i sd e f i n e d a sf o l l o w i n g ： y 旧( g ) ) = v ( a ) uv ( a ，) ，a n d e ( d ( g ) ) = e ( g ) u e ( g 7 ) u 叫，i = 1 ，2 ，礼) ， w ec a l li td o u b l eg r a p hd ( g ) t h e o r e m2 1l e tp nb eap a t h ，t h e n ( d ( r ) ) = 5 t h e o r e m2 2l e tw nb eaw h e e l ，t h e nx p ( d ( c n ) ) = 礼+ 2 d e f i n i t i o n3 1 1l e tga n dg 7b ec o n n e c t e dg r a p h 硒t h v ( g ) = ( “l ，? 2 2 ，) a n dv ( g 7 ) = v l ，v 2 ，) b e t w e e nga n dg 7w ea d dm a t c h i n gu i v i ，? 2 i v i + 1 ，7 2 i u i + 2 ，u t 饥+ m ，u i v i + ( 7 l 一1 ) ( i = 1 ，2 ，佗；m = 0 ，1 ，2 ，n 一1 ；i fi + m n ，i + mi st h ea d d e ri nt h es e n s eo f m o d 扎) t h e nt h e r ew i l lb eas e r i e so fg r a p h s ：g ( n l , ) n ，础k ，g 瓣，g 踹w e c a l l e dt h e mw e a kj o i no ft w og r a p h so fga n dg 7 o b v i o u s l y g 瓣= gvg t h e o r e m3 1 1 l e t 尸i nb eap a t h ，t h e n入t 2 、。( m m + 1 ) ) = a + 2 = m + 5 ( m = 0 ，1 ，2 ，佗一2 ，仃4 ) t h e o r e m3 1 2l e tgb e 0 ，1 ，2 ，n 一1 ) ；i f ni se v e n ，t h e n l 、 ac y c l e ，t h e n ) 、。t t t - v ( r 。n + 1 ) + 2 = m + 5 ( m = ，a 2 r t 。 n 。( r 。n + 1 ) ) = a + 2 = m + 5 ( m = 0 ，1 ，2 ，n d e f i n i t i o n3 2 1 f 2 9 】l e tgb eas i m p l eg r a p h ，v ( c ) = v 1 ，v 2 ，) ，2a r e 9 t w oi n d e p e n d e n ts e tp o i n t s ，g 阮】i sag r a p ht h a te v e r ) , v e r t e xo fg i sr e p l a c e db y j 1 2 t h ev e r t e xs e ta n dt h ee d g es e tc o r r e s p o n d st ot h ef o l l o w i n g ： y ( g 厶d = v ( c ) u 秽：，羁，) ， e ( g 【如】) = e ( g ) u 5 t h e o r e m3 2 2 l e tg 机3 ) b eac y c l ea n dg 蚴b e a s p l i t e dg r a p ho f g ，i f ni s e v e n ，t h e n 碍( g ) = 6 。 t h e o r e m3 2 3l e t 列b eas p l i t e dg r a p ho fc o m p l e t eg r a p h 珞，t h e n 碍( 阮】) 2 n d e f i n i t i o n3 3 1 1 1 2 1l e tt ( g ) b eat o t a lg r a p ho fg ，i t sv e r t e xs e tc o r r e s p o n d s t ot h ev e r t e xa n de d g eo fg r a p hg 。t h et w ov e r t i c e so ft o t a lg r a p ha r ea d j a c e n ti f a n do n l yi fc o r r e s p o n d i n gv e r t e x e so re d g e so fg a r ea d j a c e n t ，o rt h ec o r r e s p o n d i n g v e r t e xa n de d g ea r ei n c i d e n t l e t v ( c ) = u l ，v 2 ， ，e ( g ) = e 1 ，e 2 ，e m ) ，t h e n y ( t ( g ) ) = l ， 2 ，u 。 u v i ，j v i v j e ( g ) ) ， e ( 丁( g ) ) = 忱i 破吩e ( g ) ) u e i e jl e ia n de ja r ea d j a c e n ti nc u v l e ；l v ia n d e fa r ei n c i d e n ti ng 1 0 t h e o r e m3 3 1l e tg b eac y c l ea n dt ( g ) b eat o t a lg r a p ho fg ，t h e n 碍( t ( g ) ) 6 ；i f 礼i se v e n ，t h e n 碍( t ( g ) ) = 6 t h e o r e m3 3 2l e trb eap a t ha n dt ( p n ) b eat o t a lg r a p ho fr ，t h e n 山东师范大学硕士学位论文 硪职肛 | 礼= 2 扎= 3 扎 4 t h e o r e m3 4 1l e tgb eat r e ew i t ha ( g 、= 3 , a n da l lt h ev e r t i c e sw i t h m a x i m u m d e g r e ei so nap a t h ，t h e n a ；( g ) 5 l e tf mb eaf a na n di t so r d e ri sm + 1 , w ed e n o t ei tw i t hg 碟7 】w h e nnh e a r t s o ff a na r ec o n n e c t e di n t oac i r c l e l e t y ( g ) = v l ，v 2 ，】i ， y ( q 晶) = y ( g ) u u i j l i = 1 ，2 ，n ；j = 1 ，2 ，m ) ， e ( g f m ) = e ( g ) u v i u i j l i = 1 ，2 ，佗；j = 1 ，2 ，m u t 正巧u i j + l i i = 1 ，2 ，礼；歹= 1 ，2 ，m 一1 ) t h e nt h e r ei sat h e o r e mf o l l o w i n ga b o u t ( 2 ，1 ) 一t o t a ll a b e l l i n go fg r a p hg r t h e o r e m3 4 2i fn 三o ( m o d 2 ) t h e n 墩g 吲= 3 m = 1 m 2 i nt h ep a t h ，k ，j o i nut ovi fa n do n l yi fd ( u ，钞) = 后( 乱， y ( 尸k ) ) ，t h e nt h en e w g r a p hi sc a l l e d 磁 2 1 】【3 9 】t h e nt h e ( 2 ，1 ) 一t o t a ll a b e l l i n go f 磁i sg i v e na sf o l l o w s t h e o r e m3 4 3f o rg r a p h 磁，i fk 1 ，n 3 k + 2 ，t h e n a 多( 碟k ) = 6 i nt h ec y c l ec k ，j o i n 乱t ovi fa n do n l yi fd ( u ，u ) = k ( u ，口y ( c ) ) ，t h e nt h e n e wg r a p hi sc a l l e d 础2 2 1 t h e nt h e ( 2 ，1 ) 一t o t a ll a b e l l i n go fs o m e ( m 1 ) i s g i v e na 8f o l l o w i n g 1 1 山东师范大学硕士学位论文 t h e o r e m3 4 4f o rg r a p hc ，i fm 1 ，t h e n a 2 t k l 4 2 。) = 6 f o rc o m p l e t eg r a p h ，u ，u y ( ) ，d e l e t et h ee d g eu va n do b t a i n 一u 口 t h e o r e m3 4 5i f 礼i sa l lo d di n t e g e ra n dn 3 ，t h e n a ；( 五乙一仳口) = n + 1 l e ty ( g ) = v l ，v 2 ，) a n dv 7 ( g ) b eac o p yo fy ( g ) w i t hv 7 ( g ) = u l ，u 2 ，u n ) s o m en e wg r a p h ss n ，s r ，m ( g ) a r ed e f i n e da n ds o m er e s u l t so f 0 ，1 ) - t o t a ll a b e l l i n go ft h e ma r eg i v e na sf o l l o w i n g s 住i sd e f i n e da sf o l l o w i n g ： v ( s “) = v ( g ) u v 7 ( g ) ，a n de ( s n ) = e ( g ) u u i v i ( i = 1 ，2 ，n ) ) u u i v i + l ( i = 1 ，2 ，竹一1 ) 让。口1 ) t h e o r e m 3 5 1 i f 仡i se v e nt h e n 碡( s ”) = a + p = p + 4 f o rg r a p hs “( i fni se v e n ) ，j o i n tu l u 2 ，7 , 2 u 3 ，u n - 1 u n ，u n u la n do b t a i n 研 t h e o r e m3 5 2i f 铯i se v e nt h e n 譬( 曰) = + p = p + 4 t h eg r a p ho b t a i n e db ym s t r u c t u r ei sd e n o t e db ym ( g ) 【3 1 1 i fv ( c ) = 1 ，v 2 ，) ， t h e n y ( m ( g ) ) = v ( c ) u 口；i 仇g ，i = 1 ，2 ，n u w l w g ) ， e ( 必( g ) ) = e ( g ) u 1 皱呓f 砚g ，i ，j = 1 ，2 ，死，u g w l i g ， g 】 = 1 ，2 ，强；皱 t h e o r e m3 5 3i f 扎i se v e nt h e n 扎十p 一1 = a + p 一1sa t ( m ( g ) ) + p + 2 = n + p + 2 k e yw o r d s ：t h ep a c k i n gc o l o r i n g ；t h ep a c k i n gc h r o m a t i cn u m b e r ；，i ) - t o t a l l a b e l i n g ；( p ，1 ) 一t o t a ln u m b e r ；w e a kj o i no ft w og r a p h s ；s p l i t e dg r a p h ；t o t a lg r a p h ；g rg r a p h ；磁g r a p h ；罐g r a p h ；m y c i e l s k i a n - g r a p h 1 2 c l a s s i f i c a t i o n ：0 1 5 7 5 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得 ( 注：如没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或 证书使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意 学位做储躲副捅导师粹到磊 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅本人授权学校可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文 ( 保密的学位论文在解密后适用本授权书) 学位敝储姆刍1 1 桶导师擗 签字日期：2 0 0 9 酣磊 签字日期：2 0 0 9 午，月加 山东师范大学硕士学位论文 第一章引言 图论的研究对象是图图论中的图指的是一些点以及连接这些点的线的总体 通常用点代表事物，用连接两点的线代表事物之间的关系，图论则是研究事物对 象在上述表示法中具有的特征与性质的学科已经有2 0 0 年发展历史的图论发源 于1 8 世纪纪普鲁士的柯尼斯堡的七桥问题：当地的居民想知道能否从任意一陆地 出发，走遍连接该地的7 座桥又回到原地? 其条件是每座桥都经过一次很多人 都曾试验过，但都失败了l 欧拉把七桥问题化为一个数学问题，提出了一笔画 问题并给出其判断准则，从而判定七桥问题不存在解这是图论在萌芽时期最具 有代表性的问题在萌芽时期不少的图论问题都是围绕着游戏而提出并加以归纳 为数学问题，从而找出解决是否可行的 随着图论理论的发展，图论分出许多分支起源于1 5 0 年前的四色猜想的染色 问题有着极其重要的地位所谓的四色猜想，就是在一个平面或球面上的任何地 图都能够只用四种颜色着色，使得每个国家用一种，且没有两个相邻的国家有相 同的颜色尽管迄今为止仍没有得到非计算机的理论证明，但是人们在解决四色 猜想问题的过程中所得出的思想、方法和技巧远远超出了解决四色问题的最初目 的，并且为图论理论宝库增添了一个又一个的精彩结果生活及科学领域中许多 问题的数学模型都可以用图的形式来建立，然后对图中某些对象按照一定规则进 行分类，而这种分类方法的一种简单而直观表达