（应用数学专业论文）图的邻点可区别全染色和有全色子图限制的染色问题.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声 j 的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我同工作的同志对 c 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：移函前 导师签字：孙磊 学位论文版权使用授权书 本学位论文作者完全了解出丕垣堑盍堂有关保留、使用学位论文的规定，有权保 g 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阋。本人授 出丕! ! 巫菹盔堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 日影印、缩印或扫描等复制手段保存，汇编学位论文。( 保密的学位论文在解密后适用 k 授权书) 硒苜 导师签字：砚、彩 签字日期：2 0 07 年c 声月o r 山东师范大学硕士学位论文 图的邻点可区别全染色和有全色子图限制的染色问题 韩淑芹 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 染色问题是图论研究的经典领域，它源自于四色定理的研究，是图论研究 中一个很活跃的课题随着染色问题在现突中被广泛应用，各类染色问题被相 继提出并加以发展、应用 图g 的一个( 正常) 如染色是将七种染色分配给g 的顶点集y ( g ) ，使得 相邻两顶点的颜色不同定义色数为：x ( g ) = m i n 女l 图g 有缸染色) 类似的， 图g 的一个( 正常) 扛边染色是将种染色分配给g 的边集e ( g ) ，使得有公 共端点的两边的颜色刁i 同边色数x ，( g ) = l l l i n i 图g 有舡边染色l 。 全染色的概念是对点染色和边染色的推，“是图论染色的一个传统问题 由v i z i n g ( 1 9 6 4 ) 1 2 4 】和b e h z a d ( 1 9 6 5 ) p 5 2 6 l 各自独立提出的图的全染色是对图 的点，边进行染色使得相邻或相关联的两7 i 素染色不同图的全色数x r ( g ) = i n i n 纠图g 有一个七全染色 在全染色的基础上，张忠辅提出了邻点可区 别的全染色的概念并给出了相应的猜想和两个引理 张忠辅定义的邻点可区别的全染色如f ：设g ( k e ) 为阶不小于2 的简单 连通图，七为正整数，令映射，：y ( g ) u 引g ) 一， l ，2 ，- 一，曰对任意矿( 回， 如果 ( 1 ) 对任意u 口，” e ( g ) ，“ ，有，( u ) ，( t ，) ( 2 ) 对任意u v e ( g ) 有，( u ) ，( ) ，( “) ，( 伽) ，( 口) ，( ) 则称，为图g 的一个“全染色，简记为“丁e 若还满足 ( 3 ) 对任意u u e ( g ) ，g ( “) c ( 口) ，其中e ( “) 一 ，( ) ) u ，( 。 ) i “ e ( g ) ) 那么称，为图g 的一个缸邻点可送别全染色，简记为如a y d 7 口 图g 的全色数 1 山东师范大学硕士学位论文 且 x r ( g ) ( 或记为x ”( g ) ) = m i n 叫图g 有一全染色 图g 的邻点可区别的全色数 ) ( _ ( g ) = m i n 纠图g 有b a y d 丁c ) 张忠辅给出了关于邻点可区别全染色的两个引理 对任意阶为n 22 ) 的简单连通图g ，邻点可区别全色数x 一( g ) 存在，并 x m ( g ) ( g ) + 1 若图g ( k e ) 有两个相邻的最大度点，则有x d t ( g ) ( g ) + 2 张忠辅在文献i q 中给出了邻点可区别全色数猜想 对任意阶为n 2 ) 的简单连通图g ，有x 。t ( g ) ( g ) + 3 确定一任意给定图的邻点可区别全色数是n p 困难的目前关于路，豳， 完全图，完全二部图，星，扇，轮，树等特殊图的邻点可区别全色数已给出另外 上述特殊图的m y c i e l s l c i 图，联图和乘积图的邻点可区别全色数已有一些结果 同时，p e t e r n 图，h e a w o o d 图，t h o m a s s e n 图的邻点町区分全色数也【三得到结果 1 8 8 0 年，边染色的概念被提出，在边染色问题的研究中有著名的四色定 理1 9 6 4 年，v i z i n g 得出一个重要的定理即对任意的简单图g ，有( g ) sx ，( g ) ( g ) + 1 1 9 7 4 年，r p g u p t a 对边覆盖染色进行了研究图g 的边覆盖染色是对图 g 的所有边进行染色使得每种颜色在每个顶点上至少出现一次满足图g 有一个k 边覆盖染色的最大正整数k 称为图g 的边覆盖色数，记为疋( g ) 同年，g u p t a 证珊j 了对任意的简单图g ，有6 ( g ) 一1s 砭( g ) sd ( g ) 若 x ：( g ) = j ( g ) ，则称g 是第一类的若x ：( g ) 一j ( g ) 一l ，则称g 是第二类 的刘桂珍老师及苗连英，宋惠敏等对图的边覆盏染色进行了进一步的研究并 2 山东师范大学硕士学位论文 取得了丰硕的成果 2 0 0 6 年。孙磊老师受边覆盖染色的启发提出了全色极大团染色的概念全 色极大团染色是对图g 的顶点进行染色，使得g 的每个极大团所有颜色均出 现满足图g 有一个k - 全色极大团染色的最大正整数k 称为图g 的全色极 大团色数，记为x ，。盯( g ) 显然有x 。盯( g ) sn l i n l h | | 日为g 的极大团 本文一部分主要探讨了轮，完全图的h 叮曲s 乱m 的邻点可区剐全色数 另外还得到了特殊图璐，花g 的邻点可区别全色数另一部分讨论了特定 条件下金色极大团染色与边覆盖染色的等价性，给出了联图，复合图，笛卡尔 乘积图，外平面图的全色极大团色数，并给出了k 。一m ，磊，m y c i e l s l c i 图，类 m y c i e l s 醢图的全色极大团色数 在本文中我们主要得到结论如下 两个点不交的图g 1 和g 2 的日叮西5 u m 【1 】g = ( g l ，z l y l ) + ( g 2 ，z 2 抛) 是由g lug 2 粘合。l ，z 2 为一个点，删去边。l l ，勋抛增加边y l 驰所得其巾 o l 掣l e ( g 1 ) ，z 2 抛e ( i 吼) 令l k = k l v c ；，y ( w j ) = i ，砚， ，e ( i i ，。) = u i u + i 辞= 1 ，2 n ；+ l = 功lu 蜘仉悼= l ，2 ，一，n ) ，以为的复制 定理2 。1 1 。日酊蠡s t ；mh 名= ( 攻，q 地) + ( 1 蝶，口：磁) ，粘合吨，口；为一 个点 l ，则 f5 n = 3 x 。t ( h ：) = 6 n = 4 ln + 1 5 定理2 1 2 日巧白s “mg = ( 1 ，。o u l ) + ( w ：，嵋口：) ，粘合如，嵋为一个 点如，则 x m ( g ) = 2 n l 3 山东师范人学硕+ 学位论文 定理2 1 3h 叼6 5s n mg = ( 正。，f i 砚) + ( 犯。， ：呸) ，秸合口1 ，为一个 点 1 ，则 c g ，= 僻：二；烹篓：雾菇4 办一刮胁姗数 在含有n 个顶点的路r 上，当且仅当两点距离为k 时添加一条边，所得 的图称为磺图 4 3 j 定理2 2 1 对图磁，自= 【引，有x “( 磷) = 5 是具有n 个顶点”i j j 一，的完全图，在凰的每个顶点q 上悬挂 m ，( 1 isn ) 个点铫1 ，口i 。，这m i 个点形成一条路奶1 u 。，如此得 到花g 定理2 2 2 对花g ，不妨设m 。= m a x k l ，2 ，。m 女，有 c 铲冀翳= 尝枷 埘任意的图g 其线网( g ) 【1 l 的顶点集为e ( g ) 两点之间自边当且仅当 在图g 中两边相邻 埘任意的图g 其仝图t ( g ) 【1 l 的顶点集为v ( g ) u e ( g ) 两元素问有边当 且仅当在图g 中两元素相邻或相关联 记p = m i n i g 川g 7 为g 的极大团 ，口= m i n f 日，h 7 为h 的极大团 定理3 1 1 若存在h 使g = l ( 日) 且p24 ，则图g 的全色极大团染色等 价r 躅h 的边覆盖染色 g i l p t a 定理的内容是对任意的简单图g 有6 ( g ) l 疋( g ) 6 ( g ) 4 山东师范大学硕士学位论文 推论3 1 2g u p t a 定理等价于下面两种情形： ( 1 ) 若存在h 使g = l ( 日) 且p 4 ，则有p 一1 x 。r ( g ) p ( 2 ) 若存在h 使g = r ( 日) 且p 4 ，则有p l ，x ，。r ( g ) p m 是完全图玩的某一匹配，则一m 的所有极大团点数相同，均为 f l 一2 i m i + l 肘i = 住一i m i ，且j 厶一m 的每个极大团的点集形式为y ( 坼。) y ( m ) 与i m l 个点的并集，这l m l 个点是从m 的每个匹配边连结的两点中任意一点 组成的 定理3 1 3 完全图，ce ( k ) 且j ( 一) t l 一2 ，则x 。盯( k 。一 ) = 佗一j j 定理3 1 4g = 矗，则 c g ，= 裟萋 两个图g 和h 的联图g v 日1 1 】定义为：y ( g v 日) = y ( g ) u y ( ) ，( g v 日) = e ( g ) u e ( 胃) u “口i “y ( g ) ，口y ( 胃) 定理3 1 5 对任意简单连通图g ，h ，有x 。丁( gv 日) = x 。7 ( g ) + x 。c r ( ) 两个图g 和h 的复合图g 【日】【9 l 定义为：它的顶点集为y ( g ) 矿( 日) ，其巾 两个顶点( “， ) ，( “， ) 相邻当且仅当或者“7 e ( g ) ，或者“= “，u r e ( 日) 定理3 1 6 图g ，h 分别满足x 。盯( g ) = nx 。r ( 日) = 口，则有x 。r ( g 【卅) = x m 。埘，( g ) x m 删r ( ) 并不是对所有的简单连通图g ，h 均有。r ( g 冽) = x 。盯( g ) x 。r ( 目) 例如：g = p n 日= c k + l ，而x 。：。r ( r 【q 。+ 1 1 ) = 3 2 1 5 山东师范大学硕士学位论文 对于图g 和h ，设y ( g ) = u l ，“2 ，t 。) ，y ( 日) = l ，砚，一， 它们 的笛卡尔乘积g 日f 9 】定义为：y ( g 日) = 1 = ( 地，码) ，1 l m ，1 j n ) ，e ( g 日) = 1 “u h ， = 和研e ( 日) 或j = 明i u e ( g ) 定理3 1 7 若p 一1sx m 甜盯( g ) sp 1 口一1 x 。m 盯( 日) 口，则有 x m 。羽( g 日) = m i n x m 。；d r ( g ) ，x m 砰口，( 日) ) 我们称由m y c i e l 8 l c i 作图法口爿得到的图为m y c i 幽b 图给定图g ，其顶 点集y = 口l ，也，) 图g 的m y c i e l 8 l 【i 图( 记为m ( g ) ) 定义为：顶点 集y ( m ( g ) ) = yu i ，嵋，t ，u ) ，边集e ( f ( g ) ) = e ( g ) u u q l 仉 e ( g ) ，l ，j = 1 ，n ) u u l = 1 ，一，n 定理3 2 1 对任意简单连通图g ，均有x 。埘( m ( g ) ) = 1 定理3 2 2 对任意简单连通图g ，令1 ( g ) = m ( g ) 一 ，则x 。c r ( “( g ) ) = x 。c 丁( g ) 给定图g ，顶点集为y = t l ，地，) 图g 的类m 构造圈( 记为s ( g ) ) 定义如卜：y ( s ( g ) ) = 矿( g ) ui ，( g 7 ) u ，g 为g 的复制边集联s ( g ) ) = e ( g ) ue ( g 7 ) u 口。l q y ( g ) ，f = 1 ，2 ，n ) u 砜q l 仇q e ( g ) f j = l ，2 ，一，n u i = 1 ，2 ，一，礼) 对图s 量( g ) 定义为：s ( g ) = s ( g ) y ( s 纛( g ) ) = y ( g ) u y ( g ，) u 矿( 6 ) u u y ( g ( m ) u t j ，e ( 5 k ( g ) ) = e ( g ) u e ( g 7 ) u e ( g ”) u u e ( g ( m ) u 毋毋+ 1 i 仇 y ( g ) ，f = l ，2 ，一，n ；j = o ，1 ，一，m l ；= 扯 u 越t + 1 i u 吩e ( g ) ，f ，j = 1 ，2 ，扎；七= o ，1 ，m 一1 u u ：m 叫1 y ( g ) ， = l ，2 ，一，n ) 定理3 2 3 对任意简单连通图g ，有x 。盯( s ( g ) ) = x 。r ( g ) + l 推论3 2 4 令s 0 ( g ) = g v w ，则有x 。7 ( s o ( g ) ) = x 。r ( g ) + 1 定理3 2 5 对任意简单连通图g ，有x 。r ( s 。( g ) ) = x 。盯( g ) + 1 6 山东师范大学硕士学位论文 定理3 2 6 若g 为外平面图且p = 2 ，则 c g ，= g 麓3 腑腓舯将图 定理3 2 7 若g 为外平面图且p = 3 ，则x 。埘( g ) = 3 关键词：全染色；邻点可区别全染色；边覆盖染色；全色极大团染色 m y c i e l s l ( i 图；日叮曲8 u m 分类号：0 1 5 7 5 7 山东师范大学硕士学位论文 t h ea d j a c e n tv e r t e x d i s t i n g u i s ht o t a l c o l o r i n ga n dt h ec o l o r i n gp r o b l e mt h a tb e s u b m i t t e dt o t h et o t a lc o l o r s s u b g r a p h s h u q i n h s c l l o o lo fm a t h e m a t i c a ls c i e n c 鹤，s h a i l d o n gn o r m a lu n i v e r 8 i t y j i n 柚，s h 8 i l d o n g ，2 5 0 0 1 4 ，p r c h i n a a b s t r a c t t h ec o l o r 堍p r o b l e mi so n eo f 嘶m a r y 丘e l d si nt h es t u d vo fg r a p ht h e o r i e s i t i sf r o mt h e8 t u d yo ft h ec e l e b r a t e df o u rc 0 i o rp r o b l e m w i t ht h ea p p i i c 8 t i o no f t h ec o l o r i n gp r o b i e ms o m es c h o l a r 8p r 卿n e da n ds t u d i e d8f 音wc o l o r i n gp r o b l e m w i t hd i h b r tr e g t c t i o n a ( p r o p e r ) 七c o l o r i n g o f g r a p h g i s a n a 筠i g n m e n to f o n e o f | c o l o r s t o e a c hv e 卜 t e xi ns u c haw 町t h a a d j a c e n tv e r t i c e sha _ v ed i s t i n c t l o r s d e 丘n et h ec h r o m a t i c n u m b e ro fg 硒x ( g ) = m i n 七i g r a p hg h 粕“c o l o r i n g s ) s i m i l a r ，a ( p r o p e r ) 缸e d g e - c o l o r i n go fg r a p hg i sa na s s j g n m e n to fo n eo f 七c o l o 鸺t oe a c h 酣g e8 0t h a tn o t w oa 由a c e n te d g e sh a v et h es a m ec o l o r t h ee ( k e - c h r o m a t i cn u m b e ri sd c 丘n e da s x ，( g ) = m i n i g r a p hgh a s 一e d g e c o l o r i n g s ) t h et o t a lc o l o r i n gi sag e n e r a l i z a t i o no f t h ec o l o r i n ga j l dt h ee d g ec o l o r i n g i t s at r a d i t i o n a lc o l o r i n gp r o b l e ma n dw a si n t r o d u c e db ，tv i z i n g ( 1 9 6 4 ) a n di n d e p e n - d e n t 玲b e h z a d ( 1 9 6 5 ) t h et l t a l l o r i n gi sd e 丘n e d 嬲a uo fv e r t i c 够a n de d g o f t h eg r a p ha r ec o i o r e di n 叫c ha 硼l yt h a tn ot w oa d j a c e n to ri n c i d e n te l e m 朗t s 盯e c o l o r e d 乞h es 啪e t h et o t a lc h r o m a t i cn u m b e ri sd e 6 n e da sx 丁( g ) = m i n f 七l gh 够 缸t c ) o nt h eb a s i so fc h ec o t a ic o l o r i n g ，z h a n gz h o n g f up r e s e n t e dt h ec o n c e p t o ft h ea d j a c 朗tv e r t e x - d i s t i n g u i s h i n gt o t a lc o l o r i n g sa n dg a v et h ec o n j e c t u r ea | l d t w or e s u l t s t h ed e f l n i t j o no f 删a c e n tv e r t e x - d i s t i n g u i s h i n gt o t a lc o l o r i n gb yz h a n gz h o n g f u i sa sf o l l o w s ：l e tg ( y ( g ) ，e ( g ) ) i sas i m p l ec o n n e c t e dg r a p ho fw h i c ht h eo r d e ra ti e 粥t2 ，七i sap o s m v ei n t e g e ra i l d ，i sam a p p i n gf r o my ( g ) ue ( g ) t o 8 山东师范大学硕士学位论文 1 ，2 ，) f 0 r8 n yt y ( g ) ，i f 1 ) f b r 蛐y 删，仇p e ( g ) ，u 伽，t h e 弛i s ，( “口) ，( ”) 2 ) f 曲a r l y “v e ( g ) ，t t l e r e8 r e ，( t ) ，( u ) ，( 乱) ，( t 钉) ，( u u ) ，( ) t h e n ，i sc a l l e dab t o t a lc o l o r i n go fg r a p hg 锄dt h et o t a l - d l r o m a t i c 眦m b e ri 8 d e b n e d 鹪x r ( g ) ( o rd e n o t e d 嬲( g ) ) = m i n 叫g r a p hgh 缸t o t “- c d l d r i n g s ) i f ，札s os a t i s 6 皤 3 ) f o r 蛆y t e ( g ) ，t h e r e i s c 似) c 扣) ；w h e r e e m ) = ，( t ) u ，( u ) i t e ( g ) i sc a l l e d t h e l o rb e to fv e r t e 】【t t h e n ，i 8 c a i i e daka d j a c e n tv 既t e x - d i s t i n g u i s h i n gt o t a lc 0 1 0 r i n go f g r a p hg ( b r i 胡y n o t e d 够缸a v d t c ) 彻d c ( g ) = m i n 七i gh 鸽“a 、，d t c ) i sc a l l e dt h ea d j 8 c e n t v e r t e x - d i s t i n g u i s h i n gt o t mc h r o m 8 t i cn u m b e ro fg r a p hg z h a n gz h o n g f up r 朗e n t e dt w oi m p o r t e n tr e s u l t sa b o u tt h ea d j a c e n tv e r t e x - d i s t i n g u i s h i i 培t o t a lc o l o r i n g f o ra n ys i m p l ec o n n e c t e dg r a p hg o f o r d e rn ( n 2 ) ，a d j a c e n tv e r t e x d i s t i n g t i i s h i n gt o t a lc h r o m a t i cn u m b e rx o ( g ) e ) c s i t s ，a n d x “( g ) ( g ) + l j f 联y ( 回，f g ) ) h a st w oa d j 8 c e n tm 8 x i 锄】md e g r e ev e r t i c 黯，h e nx 。“g ) ( g ) + 2 t h et w or 晒u l t sa b o u tt h ea d j a c e n tv e r t e d j s t i n g u i s h i n gt o t a lc o l o r i n ga r e r i g h ta p p a r e n b t h ef o l l o w h l gc o n j e c c u r ei sp r o p e db yz h a n gz h o n g f u f b ra i l ys i m p l ec o i h l e c t e dg r a p hgo f o r d e rn ( n 2 ) ，t h e nx 耐( g ) ( g ) + 3 t h ep r o b i 咖o fd e t e r m i n i n gt h ea d j a c e n tv e r t e x d i s c i n g u i s h i n gt o t a lc h r o m a t i cn u m b e ro fag r a p hi sn p h 8 r d i np r e s e n t ，w eo b t a i nt h ea d j a c e n tv e n e 静 9 山东师范大学硕士学位论文 d i s t i n g u i s h i n gt o t a lc h r o m a t i cn u m b e rf o rs p e c i a lf 印h 8s u 曲鹤p a t h ，c y c l e ，c o m p l e t e g r a p h ，2 一c o m p k t e 窜a p h ，s t a r ，沁，w h e e l ，t r e ee t c ，w ba l o b t a i nt h ea d j a c 锄t v e r t e x _ d i s t i n g u i s h i n gt o t a lc h r o m a t i c 肌m b e rf o rt h em y c i 幽l c ig r a 曲，l i n kg r a p h ，t h ec a r t e - s i p r o d u c tf a p h ，p e t e r 呦蓼b p h ，h e 删o o df 印h ，t h o m a s s e ng r a p he r c t h ee 始h 0 1 0 r i n gp r o b k mw 酗p i 8 e di n1 8 8 0i nr e l a t i o n 吡ht h ew e l l l c l l o w n f o u r - c o l o rc o n j e c t u r e i n1 9 6 4 ，z i n gp r o v e dt h e 妇n o u sv i z i n g st h e o r 锄：( g ) s ( g ) ( g ) + lf o r a i 猡s i m p l e g r a p h g i n1 9 7 4 ，r p g u p t as t u d i e dt h ee d g ec o v e rc o l o r i n gp r o b l e m t h ee d g ec o v e r c o 崎i n go f a f a p h g i s t oc o l o r “l t h ee d g 眵o f g t h a te 础c o l o ra p p e a r 8a t e 8 c 电v e r t e xv8 tk 淞to n c e t h em a x i m u mp o s i t i v ei n t e g e rks u c ht h 缸gh a s8 k - e d g ec o v e r c o l o r i n gi sc a l l e dt h ee d g ec o v e rc h r o m a t i ci n d e ) 【o fg a i l di sd e n o t e d b yx ：( g ) ag r a p hg i ss a i dt ob eo ft y p ec ii fx ：( g ) = 6a n do ft y p ec i ii f ：( g ) = j 一1 g l i u ，l m i a 0 姐dh s o n gs t u d i e dt h ee d g eo m rc o l o r i n gp r o b l e 脚 a n dg o tm 8 n yr e s u l t s i n2 0 0 6 ，l s u np r o s e dt h ec o n c e p to ft h et o 锄c o l o r sm a x i m a lc l i q u 妫( v e r t e x ) c o l o r i n g at o t a lc o l o r sm x i m a lc l i q u 鹤c o l o r i i l go fg r a p hgi sav e r t e c o l o r i n g s u c hc h a ta hc o l o 糟a p p e a ra t 髓c hm a x i m a ld i q u eo fg r 8 p hg t h em a d c i m u m n u m b e ro ft o t a lc 0 1 0 r sm a ) c i m a jc l i q u 酷c o l o r i n go fgi sc a l l e dt o t a lc o l o r sm a x i m a lc l i q u e sc h r o m a t i cn u m b e ra n dd e n o t e db yx m c r ( g ) a p p a r e n t l h x m 叮c r ( g ) m i n i h l l 日i sam a d c i m a lc l i q u eo fg r a p hg ， l nt h i st h 鹪i s ，t h e6 r s tp a r td e a l s 谢t ht h ea d j a c e n t 、，e r 。t e x - d i s t i n g u i s h i n gt 0 - t a lc h m m a t i cn u m b e rf o r 日叮曲s u mo fw h l ，c o m p l e t eg r a p ha i l dw eo b t a i n t h ea d j a c e n tv e r t e x - d i s t i n g u i s h i n gt o c a lc h r o m a t i cn u m b e rf o rg r a p h 群，n o w e r g t h es e c o n dp a r tf o c t i s e so n 如ee q u i v a l e n c e t o 翻l o 措m a ) ( i m a lc l i q u 籍c h f o - m a t i cn u m b e ro ft h el e x i c o g r a p h i cp r o d u c t ，t h ec a r e t s i a 皿p r o d u c to fg r a p h ，i i n k g r a p h ，t h eo u t e rg r a p h g r a p h 玩一，g r a p hc k ，m y c i e k k ig r 印h ，s i m i l a rm y c i e l s k i g r a p h 7 奄b f i e n ys u m m e r i z eo u rm a i nr e s u l t s f 0 1 l o w ： 山东师范大学硕士学位论文 l e tg 1 帅dg 2b ev e r t e xd 两o i n t 铲a p l l s ，c o n t a m i n ge d g e sz l 掣l e ( g 1 ) 粕d z 2 驰e ( g 2 ) t h e 日叮西s “m 1 1 jg = ( g l ，z l 剪1 ) + ( g 2 ，z 2 耽) o ft h ep a i r b ( g l ，z l ! ，1 ) a n d ( g 2 ，z 2 轨) i so b t 曲埘f r o mg l u g 2b yi d e n t i 跏n gz la n d 锄，d e l e t i n g t h ee d g e l ”l ，勋妇，a n da d d j i 培t h ee d g e 玑珈，。 l e t i = 托v 磊，y ( p ) = t 口1 ，抛，t ，n ，t ，o ) ，e ( 1 ) = 址饥+ l i = 1 ，2 ， 叫 。+ 1 ；”1 ) u 伽地悼= 1 ，2 ，l ，h 名i s t h ec o p yo f u 名 t h e o r e m2 1 1 冒酊由鼬m - 诧= ( f ，口l 忱) + ( w ：，嵋) i d e n t 萌荡姐8 n d 鹞口1 ，t h e n f 5肟3 x 越( w 公) = 6 n = 4 l 扎+ l竹5 t h e o r e m2 1 2 日幻曲5 u mg = ( ，如口1 ) + ( w ：，口i ) i d e n t 墒鹤蛳8 n d 嵋，t h e nx 毗( g ) = 2 ，l 1 t h e o r e m2 1 3 日n j 曲s 牡mg = ( k 。，”l 也) + ( 耳n ，u i 呓) i d e n t i 丘e s ia n d 嵋弱f l ，t h e n x 。t ( g ) = 扎m 4 o rn = m = 4d rn m = 4 口佗dn 1 5e 分帆扎“仃1 6 e r n m = 4c u l d 住 s 口d d 札“竹1 6 e r g r a p hr i sap a t hw h i c ht h eo r d e r i sn g r a p h 璐i so b t a i n e df r o ma d d i n g a ne d g et og r a p hri f a n do n l yi f t h ed i s t a n c eo f t w 0 诡r t i o e si 8k t h e o r e m2 2 1f o rg r 印h 磁，自= 吲，t h e r ei sx n t ( 磺) = 5 g r a p hj 厶i sac o n l p l e t eg r 印hw h i c ht h ev e r t i c e 8i 8 ”l ， n f l o 、v e rg i s o b c a i n e d f r o m8 d d i n g t h ev e r t i o 明地l ，砘2 ，奶，l 。t o t h ev e r t i c e qo f 托撕n k i n g t h ev e r t i c 船q l ，忱，r ，仃l m 。t ot h ep a t hu l 钉2 一，饥州 ，童h e o r e m2 2 2f o rn a w e rg ，l e tm = m a x 七篁l 加一m i ，t 如n 妇= 豫揣冀：竺竺m l 1 1 3 2 一 一 n n + + m m ，、l 生垄壁薹查兰堡圭兰堡堡苎 ： f 0 ra n yg r 印hg ，i t 8l i 聃g r a p hl ( g ) 1 1 i sd e f i n e d 髂：v e r t 旺s e ti se ( g ) ，t h e r e i s 肌e d g e i n t w ov e r t i c 鹤o f g r a p hl ( g ) i fa n do n l y i f t w oe d g 络ma d j a c 呲i n g r 印h g f b r8 n yf a p hg ，i t st o t a lg r a p hr ( g ) 【l li sd e 矗n e d 够：v e r t e xs e ti 8y ( g ) u e ( g ) ，t h e r e j 8a ne d g e i n t w o e l 锄e n t 8o fg r 8 p h 丁( g ) i f 蛐d 彻峥i f t w oe l e m 印t s a r ea d j a c e n to ri n c i d e n ti i lf a p hg l e tp = m i n 引g ，i i g ，i sa m a 五m a lc h q u eo f g r 印h g ，口= m i n 1 日1 1 日7 i sa m 砌m a lc q 眦o f 舒印hh ) t h e o 舱m3 1 1i f g r 8 p hg i 8t h ei i n eg r a p ho fha n dp 4 ，t h 髑t h e o _ t 8 lc o b r s m a x 两a l d b 叩鹧c o l o r i n go f g 蛐d t h ee d g ec o v e r e dc o l o r i n go f h 盯e e q u i l l e n t c o r o l l a r y3 1 2g u p t a ，st h e o r e mi se q u i v a l e mt ot w oc 够瞄柏f 0 i i o w ： ( 1 ) i f g i s t h e l i n eg r 印ho f ha n d p 4 t h e n p 一1 x 倒r ( g ) s p ( 2 ) i fg i st h et o t a lg r a p ho f ha n d p 4 t h e n p 一1 x ，n 盯c r ( g ) s p ti 8t h em a t c ho ft h ec o m p l e t e 铲a p h 戤t h e na l lm “i m a lc l i q u 酋n u m b e r o f 一m i ss 锄ea n d i sn 一2 吖l + i ，l = n l t h e v e r t e xs e to f a n y m a ) c i m a lc i i q u e0 fk 一a fi st h eu n i o no fy ( 。) y ( ，) a n dt h ev e r t i c 镐w h i c ha r e o b c a j n e df o mt h em a c he d g e so fm t h r e m3 1 3f o r t h ec o m p l e t eg r a p h 玩，c e ( ) 卸d6 ( 一) n 一2 ，t h e nx 。盯( k 。一) = n 一 1 t h e o r e m3 1 4l f g = 磊，n 坨n c g ，= ；冀淼舞 t h e l i n kg r 印h g v h e l lo fg r a p l l ga l l dg i | d p h h i sd c f i l i c d 躺f o l l u w ：y ( g v 月) = y ( g ) u 矿( ) ，e ( g v ) = e ( g ) u e ( ) u ”l u y ( g ) ，口y ( 日) 坐查堕堕奎兰堡圭堂垡堡壅 t h e o r e m3 1 5f 0 ra ys i i n p kc o n n e c t e dg r 印hg ，h ，t h e nx 肌埘( g v 日) = x 舢唧r ( g ) + x 舢。c r ( 日) t h el e 虹c 3 9 r a p h i cp r o d u c tg r a p hg f 嚣j 【9 1o f 聊hga n d 脚hh j sd e 矗n e d t ob eag r a p h 诵t hy ( g 【日】) = y ( g ) y ( 日) a n de ( g 【日】) 一 ( o ，z ) ( 6 ，y ) k 6 e ( g ) d r 口= 6 口以z e ( 日) ) t h r e m3 1 6i fg r a p hg ，h 鳃t i s 每x m 删，( 固= nx m 删( 卿= 吼t h e n x m 。村( g 【日】) =