（应用数学专业论文）两类特殊图类的路和圈问题.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名：乜秀 导师签字： 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权趁可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名： 签字日期：2 0 0 汐年尹月，日 ，、 导师签字： 签字日期2 0 0 移年伊月岁日 山东师范大学硕士学位论文 两类特殊图类的路和圈问题 沈雷 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 图的路和圈问题是图论中一个十分重要而且活跃的研究课题有大量的实 际问题可以归结为图的路和圈问题图论中三大著名难题之一的h a m i l t o n 问题本 质上也是图的路和圈问题国内外许多学者对此问题作了大量的研究工作这方 面的研究成果和进展可参见文献f 4 0 1 一f 4 3 1 其中度条件和邻域并条件成为研究路 和圈问题的重要途径，在这方面取得了很多优秀的成果经过几十年的发展，图 的路圈性质所涉及的内容日益丰富和具体路的方面包括图的h a m i l t o n 路f 可迹 性) ，齐次可迹性，最长路jh a m i l t o n 连通泛连通：路可扩等等：圈的方面包括图 的h a m i l t o n 圈，最长圈，( 点) 泛圈，完全圈可扩，点不交的圈圈覆盖等等 由于直接研究一般图的h 锄i l t o n 问题往往比较困难，于是人们转而研究不 含有某些禁用子图的图类继b e i n e k e l 9 6 8 ，1 9 7 0 年发表的关于线图性质的两篇 文章f 1 6 1 一f 17 1 之后人们开始关注包含着线图的无爪图7 0 年代末8 0 年代初是 研究无爪图的一个非常活跃的时期关于无爪图方面的部分优秀成果可参考f 2 1 - f 4 1 ，f 1 8 1 - 3 3 1 另外。无爪图的概念也被从不同角度推广到了更大的图类，如半 无爪图，几乎无爪图，( 虬4 ：2 ) 一图d c t 图等1 9 9 8 年，a a i n o u c h e 在 3 5 中定义了 一种包含无爪图的更大的图类半无爪图，且给出了关于半无爪图的路和圈方面 的一些结果之后i 艮多专家学者相继做了大量的工作来研究这类图h a m i l t o n 问 题且将无爪图中的许多非常好的结果推广到了半无爪图其中某些进展可参 考3 6 1 - 3 8 1 2 0 0 3 年，滕延燕，尤海燕，蔺厚元等在无爪图的基础上提出了k 1 4 受限图 的概念( 后者称之为( k 1 4 ：2 ) 图) ，它包含无爪图类，并且无爪图的很多结果可以推 广至( k l ，4 ；2 ) 图本篇论文主要研究了半无爪图，( k 1 4 ；2 ) 图的路和圈问题 在第一章中，我们主要介绍文章中所涉及的一些概念和术语符号，以及本文 的研究背景和已有的一些结果 在第二章中，我们主要研究了三角连通的( k 1 4 ；2 ) 图完全圈可扩性，得到下面 的结果： 定理2 4 顶点数不小于3 ，无孤立点，爪心独立的三角连通( 风4 ；2 ) 一图是完全 圈可扩的 1 山东师范火学硕士学位论文 2 在第三章中，讨论了半无爪图在不同连通度下关于路和圈的几个结果： 定理3 2 4 设g 是阶为n 3 的连通半无爪图，如果对任意不相邻的顶点z ，都 有2 f ( z ) u ( y ) f + d ( z ) + d ( y ) 2 竹一5 成立，则g 是可迹的 推论3 2 5 设g 是阶为n 3 的连通半无爪图，如果对任意不相邻的顶点z ，! ，都 有j ( z ) u ( 芗) l 学，则g 是可迹的 定理3 3 5 设g 是阶为n 3 的2 一连通半无爪图如果对每对不相邻的顶点z ，有 2 i ( z ) u ( y ) i + d ( z ) + d ( y ) 2 扎一5 ，则g 是h a m i l t o n 图 推论3 3 6 设g 是阶为礼3 的2 连通半无爪图如果对任意不相邻的顶点z ，都 有l ( z ) u ( 钞) i 呈学，则g 是h a m i l t o n 图 定理3 4 2 设g 是阶n 3 的3 - 连通的半无爪图若对g 中任意3 个顶点的独立 集 z 1 ，z 2 ，z 3 ) ，有d ( z 1 ) + d ( z 2 ) + d ( z 3 ) 礼+ 1 ，贝0 g 是h 锄i l t o n 连通图 定理3 5 3 设g 是一个阶为礼( n 3 ) 的2 连通半无爪图连通度为南 ( 1 ) 如果对于每一个七十1 个点的独立集s ，对任意让，u s ，都有 ( 札) u ( u ) i 丝= ；生丛贝0 g 是h a m i l t o n 图 ( 2 ) 如果对于每一个七+ 1 个点的独立集s ，对任意札，u s ，都有f ( 扎) u ( u ) l 竹一七一s ，则g 是h a m i l t o n 图 在第四章中，研究了半无爪图不含禁用子图日时的齐次可迹性，证明了下面 的结果： 定理4 3g 为直径至多为3 的2 连通的半无爪图，若g 不含同构于日的导出子 图，则g 为齐次可迹的 关键词：( k l ，4 ；2 ) 一图；半无爪图；邻域并；完全圈可扩；h a m i l t o l l 性；( 齐次) 可 迹性 分类号：0 1 5 7 5 山东师范大学硕士学位论文 p a t h sa n dc y c l e so ft w oc 1 a s s e so fg r a p h s l e is h e n s c h o o lo fm a t h e m a t i c a ls c i e n c e s ，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 r c h i n a a b s t r a c t t h ep r o b l e mo np a t h sa n dc y c l e so fg r a p h si sav e r yi m p o r t a n tp r o b l e mi ng r a p h t h e o r ya n dt h er e s e a r c hi sa l s oa c t i v e m a 码7p r a c t i c a lp r o b l e m sc a nb ea t t r i b u t e d t ot h ep r o b l e mo fp a t h sa n dc y c l e s w h a ti s m o r e ，t h ef a m o u sh a m i l t o np r o b l e m b e l o n 伊t ot h ep r o b l e mo fp a t h sa n dc y c l e so fg r a p h si ne s s e n c e m a n ys c h o l a r sa t h o m ea n da b r o a dm a d ea1 0 to fr e s e a r c hw o r ko nt h i si s s u e ，t h er e s e a r c hr e s u l t s a n dp r o g r e s si nt h i s 盯e ac a nb ef o u n di nl i t e r a t u r e 4 0 4 3 t h ec o n d i t i o no fd e g r e e a n dn e i g h b o r h o o du n i o n sb e c o m e sa ni m p o r t a n tw a yt os t u d yt h ep r o b l e m s i nt h i s r e s p e c t a1 0 to fo u t s t a n d i n ga c h i e v e m e n t sh a v eb em a d e a 行e rt h ed e v e l o p m e n tf o r d o z e n so fv e a r s ，t h ec o n t e n t si np r o p e r t i e so fg r a p h s p a t ha n d c y c l eb e c o m em o r ea n d m o r er i c ha n ds p e c i f i c t h ep r o p e r t i e so fp a t hi n c l u d eh a m i l t o np a t h ( t r a c e a b i l i t y ) ， l o n g e s tp a t h ，p a n c o n n e c t i v i t y ，p a t he x t e n d s i b i l i t ya n ds oo n ；t h ep r o p e r t i e so fc y c l e i n c l u d eh a m i l t o nc y c l e ，l o n g e s tc y c l e ，( v e r t e x 一) p a n c y c l i c i t y ，v e r t e x d i s j o i n tc y c l e ， c y c l ee x t e n d s i b i l i t ya n ds oo n h o 他v e r ，w ec a nn o td e n 、，t h ef a u c tt h a ti ti su s u a l l yv e r yd i 伍c u l tt os t u d y h a m i l t o np r o b l e mi nt h o s eg r a p h sw i t h o u ta n yr e s t r i c t i o n t h e nw et u mt oe x p l o r et h eg r a p h sn o tc o n t a i n i n gs o m ef o r b i d d e ns u b g r 印h ss u c ha l sc l a w - f r e e 耵印h s t h ef i r s tm o t i v a t i o nf 6 rs t u d y i i l gp r o p e r t i e so fc l a 、- f r e eg r a p h sa p p a r e n t l ya p p e a r e d f r o mb e i n e k e sc h a r a c t e r i z a t i o no fl i n eg r a p h si n 1 6 】- 17 】 h 伽怕v e r ，t h em a i ni i n - p u l s et h a tt u r n e dt h ea t t e n t i o no ft h eg r a p ht h e o 巧c o m m u n i 可t ot h ec l a s so fc l a 瓢，- 行e eg r 印h sw a s 酉v e ni n1 a t e7 0 sa n de a n y8 0 s s o m ef a m o u sr e s u l t sa b o u tc l a 肌 矗e eg r a p h sc a nb es e e ni n 【2 【4 】， 18 一 3 4 i na d d i t i o n ，t h ed e f i n i t i o no fc l a 瓢，- f e e g r a p hh a sb e e ne x t e n d e dt os e v e r a l l a r g e rg r 印hf 锄i l i e si nd i 能r e n tv i e w s ，s u c ha s q u a s i c l a 飘，f t e eg r a p h s ，a l m o s tc l a w 一e eg r a p h s ，( k l ，4 ；2 ) 一g r a p h s ，d c tg r a p h se t c a a i n o u c h e 【3 5 d e 丘n e dan e wg r a p hf a m i l y - q u a u s i - c l a 、v - 丘e eg r 印h sa n dh ea l s og a e s e v e r a lr e s u l t sa b o u tp a t h sa n dc y c l e si nt h en e wg r a p hf a m i l y a f c e rt h a t ，m a n yr e s e a r c h e r sh a ed o n ea1 0 to f ，o r kt os t u d yh a m i l t o np r o b l e mi n q u a s i - c l a w 丘e e g r 印h s 3 6 】- 3 8 】i n2 0 0 3 ，t e n gy a n y a j l ，y o uh a i y a n ，l i nh o u y u a ng a et h ed e f i n a t i o n 3 4 o fk 1 4 - c o n 丘n e dg r a p h s ( t h e 】a t t e r n a m e d ( k l ，4 ；2 ) 一g r a p h s ) w h i c hc o n t a i nt h ef a m i l y o fc l a w 矗e eg r a p h s m a n yg o o dr e s u l t so fc l a w - f r e eg r a p h sh a v eb e e ne x t e n d e dt o ( k i ，4 ；2 ) 一g r a p h s i nt h i sp a p e r w em a i n l ys t u d yt h ep a t h sa 1 1 dc y c l e so fq u a s i c l a w f r e eg r a p h sa n d ( k 1 ，4 ；2 ) 一g r a p h s i nt h ef l r s tc h a p t e r ，w eg i v eab r i e fi i l t r o d u c t i o na b o u tt h eb a s i c c o n c e p t s ， t e r m i n o l o 百e sa n ds y m b 0 1 sw h i c hw i l lb eu s e di nt h i sp a p e r i nt h em e a n t i m e ，w e a l s og i v es o m er e l a t e dr e s e a r c hb a c k g r o u i l d sa n ds o m ek n o ，nr e s u l t s ， i nt h es e c o n dc h a p t e r ，w em a i n l yo b t a i nt h er e s u i to f ( k 1 4 ；2 ) 一目a p ha sf 0 1 l o w s ： t h e o r e m 2 4e v e 搿t r i a n g u l a r l yc o n n e c t e d ( 1 ，4 ；2 ) 一g r a p hw i t hi n d e p e n d e n t c l a wc e n t e r sa n da tl e a s tt h r e ev e r t i c e sa n dw i t h o u ta n yi s o l a t e dv e r t e xi sf u l lc y c l e e x t e n d a b l e i nt h et h i r dc h a p t e r ，伦m a i n l ys t u d yt h ep a t h sa n dc y c l e so fq u a s i c l a 甩卜f e e g r 印h sa n dg i v et h ef 0 1 1 鲫i n gr e s u l t s ： t h e o r e m 3 2 4l e tgb eac o n n e c t e dq u a s i d a w 岳e eg r a p ho f o r d e r 扎3 i f f o ra n yd i s t i n c tv e r t i c e sz a n d ，t h ei n e q u a l i 盼2j ( z ) u ( 耖) i + d ( z ) + d ( ) 2 ，z 一5 h o l d s t h e ngi st r a c e a b l e c o r o l l a r y 3 2 5l e tgb eac o n n e c t e dq u a s i c l a 瓢k 仔e eg r a p ho fo r d e r 佗3 i ff o ra n yd i s t i n c tv e r t i c e sz a n d 矽，t h ei n e q u a l i t yl ( z ) u ( 可) l 呈学h 。1 d s t h e n gi st r a c e a b l e t h e o r e m 3 3 5l e tgb ea2 - c o n n e c t e d q u a s i c l a w - 矗e eg r a p ho fo r d e rn 3 i f f o r 龇1 yd i s t i n c tv e r t i e e sza n dy ，t h ei n e q u a l i t y2 l ( z ) u ( y ) i 十d ( z ) + d ( 妙) 2 礼一5 h o l d s ，t h e ng i sh a m i l t o n i a n c o r o l l a r y 3 3 6l e tgb ea2 一c o n n e c t e dq u a s i c l a r - 矗e eg r a p ho fo r d e rn 3 i f f o ra n yd i s t i n c tv e r t i c e sz a n d 夕，t h ei n e q u a l i t yj ( 。) u ( 矽) l 学h 0 1 d s ，t h e ng i sh a m i l t o n i a n t h e o r e m 3 4 2l e tgb ea3 - c o n n e c t e d q u a s i c l a w f r e e 铲a p ho fo r d e rn 3 i ff o ra n yi n d e p e n d e l l ts e t s _ ( z 1 ，z 2 ，z 3 ) o ft h r e ev e r t i c e si ng ，t h ei n e q u a l i t yd ( z 1 ) + d ( z 2 ) + d ( z 3 ) 礼+ 1h o l d s ，t h e ngi sh a m i l t o nc o n n e c t e d t h e o r e m 3 5 3l e tgb eaq u a s i c l a w - 矗e eg r 印ho fo r d e r 佗3w i t hc o n n e c - t i v i t y 七 山东师范大学硕士学位论文 ( 1 ) i ff o ra n yd i s t i n c tv e r t i c e s “a n d i na n yi n d e p e n d e n ts e t so fc a r d i n a l i t y 后+ 1 ：i ( 让) u ( u ) l 盈号半h o l d s ，t h e ng i sh 锄i l t o n i a n ( 2 ) i ff o ra i l vd i s t i n c tv e r t i c e sua n dui na n yi n d e p e n d e n ts e t so fc a r d i n a l i t y 露+ 1 ，i ( u ) u ( f ) l n 一七一sh o l d s ，t h e ng i sh 锄i l t o n i a n i nt h ef o u r t hc h 印t e r ，聘m a i n l y 百v et h er e s u l to fh o m o g e n e o u s l yt r a c e a b l e t h e o r e m 4 3i fgi s2 一c o n n e c t e dq u a s i - c l a w 一仔e eg r a p ho fd i a m e t e ra tm o s t3 w i t h o u ti n d u c e ds u b g r a p hi s o m o r p h i c 日，t h e ng i sh o m o g e n e o u s l yt r a c e a b l e k e y w o r d s ： ( k 1 4 ；2 ) 一伊a p h s ：q u a s i c l a 肌行e eg r a p h s ；n e i g h b o r h o o du n i o n s ： f u l lc y c l ee x t e n d a b l e ：h a m i l t o n i a n ；( h o m o g e n e o u s l y ) t r a c e a b l e ，h a m i l t o nc o n n e c t e d c l a s s i f i c a t i o n ： 0 1 5 7 5 5 山东师范人学硕士学位论文 6 第一章预备知识 1 1符号概念介绍 本文仅考虑有限无向简单图，所使用的记号和术语约定如下，其中未加说明 的部分请参照文献 1 设g 是一个图，v ( g ) ，e ( g ) 分别表示g 的顶点集和边集对于u y ( g ) ，s ：丁， b ，f y ( g ) ，令 ( 口) = 钆y ( g ) ：u 钞e ( g ) ) ? 【u = ( u ) u u ) k ( u ) = j 7 v ( 口) nb ， k ( f ) = u 。f b ( u ) e ( s ，t ) = s e ( g ) ：s s ，丁) 图g 的由s 导出的子图记为( s ) 将图g 中与f 关联的边的数目叫做顶点u 的度， 记为d g ( u ) ，即d g ( u ) = i ( u ) i 在不引起混淆的前提下也简记为d ( u ) 用如，g 分 别表示g 中顶点的最小度和最大度也常简记为6 如果图g 中不存在七一1 个顶点的集合分离g ，则称g 是七一连通的图g 的连通 度k ( g ) = m a x 豇：g 是七一连通的) 若对任意t j y ( g ) ，( ( t 啪是连通的，则称图g 是 局部连通的对于任意一对边e 1 ，e 2 e ( g ) ，在g 中存在一系列3 一圈g ，q ，g 使 得e 1 c 1 ，e 2 a 且e ( g ) ne ( g + 1 ) 0 ( 1 i z 一1 ) ，则称图g 为三角连通的 令图( g ) = ( v ( 锯( g ) ) ：e ( 锯( g ) ) ) ，其中y ( 锈( g ) ) = c i c 为g 的3 一圈) ， e ( ( g ) ) ) = a q i g ，q y ( 铭( g ) ) 且e ( c - ) ne ( g ) 仍) 由三角连通的定义易知，三角连通具有下述性质： 性质1 图g 为三角连通当且仅当 ( 1 ) 任意边e e ( g ) 都存在g y ( 够( g ) ) ，使得e e ( g ) ，且 ( 2 ) 图( g ) 为连通的 山东师范大学硕十学位论文 以g 中顶点z ，可为端点的路记为( z ：y ) 路g 中最短( z ，y ) 一路的长，称为z 和y 间 的距离，记为d ( z ，可) m ，gd ( z y ) 称为图g 的直径 设尸= z l z 2 z t 为图g 的一条路z i 一7 y ( j p ) ( 1 i j ) ，用z _ 7 和z 产2 分 别表示p 上的点z 川和z 州，其中z 产1 ，z 产2 和z _ 1 ，z - 2 也分别记为z 产z 产+ 和z _ z _ 一； 用z i p 巧和q 瓦i ( f 歹) 分别表示尸的子路筋z 州巧和巧巧一l z i 设c = u 1 也坼u 】是图g 中的圈，优，y ( c ) ( 1 i 歹r ) ，用u _ 7 和f 产2 分 别表示c 上的点饥一f 和+ f 其中f f l ，z _ 2 和u 产1 ，z 2 也分别记为町，z _ 一和u 产z r ； 用佻c ? o 和确分别表示c 上的路+ 1 z o 和地毪一l ( 这里点的下标均模r ) 经过g 中每个顶点恰好一次的路( 圈) 称为( g 的) h 1 1 i l t o n 路( 圈) 若g 中存在 一个h a m i l t o n 圈，则称g 是哈密顿的如果对于g 中任意两个顶点z ，y ，都存在以z ：可 为端点的h 锄i l t o n 路，那么称图g 为h a m i l t o n 连通的对于g 中任意的顶点z 及任意 满足3 z i g l 的整数f 都存在经过z 的长度为2 的圈，则称g 是点泛圈的如果 图g 满足：( 1 ) g 的每个顶点都在长度为3 的圈上；( 2 ) 对g 中任意一个圈c ，只 要i l ，7 ( c ) i i v ( g ) j ，就存在g 的圈c 7 ，使得y ( c ) cy ( c ) 且i i 厂( c ，) i = i y ( c ) i + 1 则称g 是完全圈可扩的c 称为c 的扩圈若g 中存在一个h a m i l t o n 路则称g 是可 迹的若对g 中任意一点z ，图g 中存在一条以z 为端点的h 锄i l t o n 路，则称g 是齐次 可迹的 若g 中不含同构于k 1 3 的导出子图，则称g 为无爪图若对图g 中的任意一对 距离为2 的点z ，y ，存在u ( z ) n ( y ) ，使得m m u m ，则称g 为半无爪图 对半无爪图，令了( z ，y ) = u ( z ) n ( y ) ：m 【z 】u m ) ，则当d ( z ，3 ，) = 2 时，( z ，可) 0 显然，半无爪图类是比无爪图类更大的图类 设p 3 是整数，g 中同构于k l ，p 的子图叫g 的一佃一爪用( 铷，z l ，) 表示 以 跏，z 1 ，) 为顶点的p 一爪，并约定记号中的第一个顶点跏表示该p 一爪中的p 度顶点若对g 的任一个p 一爪( 跏，z 1 ，) 均有i e ( ( z 1 ，z 2 ，昂) ) i q ，则称g 为 7 山东师范人学硕士学位论文 8 ( k l ，p ；口) 一图易证( k l ，p ；g ) 一图一定是( k 1 。p + 1 ；g + 1 ) 图( k l ，3 ；1 ) 一图即无爪图，故 ( k 1 4 ；2 ) 一图包含无爪图，是无爪图的推广3 一爪k 1 3 中度为3 的顶点称为爪心若图 g 中爪心集为独立集则称g 为爪心独立图 一、研究背景 1 2 研究背景及已有结果 图的h a m i l t o n 性是图论研究中的热点问题之一一百多年前，爱尔兰数学家 哈密尔顿提出了这样一个问题：一个连通图有h a 面l t o n 圈的充分必要条件是什 么? 这就是著名的哈密顿问题该问题一经提出就受到广泛关注，后经研究发现 它是个n p c 问题 对图的路圈性质的研究是以哈密顿问题为起点发展起来的，相关的研究主 要集中在两个方面一是寻找图具有某些路圈性质的充分条件，二是研究某些特 殊图类的路圈性质后者中的特殊图类主要是指不含某些特定结构的导出子图 的图类，这些特定结构的导出子图又称作禁用子图无爪图就是以k 1 3 为禁用子 图的图类由于其深刻的研究背景一一线图都是无爪图，上个世纪的七八十年代 无爪图受到图论界的广泛关注，对无爪图的路圈性质的研究也是在这个时期开 始的 经过几十年的发展，图的路圈性质所涉及的内容日益丰富和具体比较常见 的路的方面有可迹性，h a m i l t o n 连通，泛连通性路可扩性等，圈的方面有哈密顿 圈，( 点) 泛圈性，完全圈可扩性等同时从无爪图的禁用子图。3 的结构出发，又 相继定义了一些新的图类，如几乎无爪图，半无爪图，( k 1 ，p ；q ) 一图等等一方面 人们尝试把无爪图中的结论推广到更大的图类另一方面人们也希望得到这些 新的图类在路圈方面的一些新的结果 基于以上研究背景，本文选择了半无爪图和( k l ，4 ；2 ) 一图中的路圈性质作为 研究的内容，主要沿着推广已有结论和探索新结果两个思路进行研究 山东师范大学硕士学位论文 二、已有结果 1 9 9 0 年g r t h e n d r y 得到下面的结果： 定理2 1 f 5 】项点数不小于3 的连通，局部连通无爪图是完全圈可扩的 2 0 0 4 年赖虹建等定义了三角连通并得到下述结果： 定理2 2 【6 】顶点数不小于3 的三角连通的无爪图是点泛圈的 曲晓英又将结果推广至半无爪图 定理2 3 f _ 无孤立点的边数不小于3 的三角连通的半无爪图是点泛圈的 1 9 8 5 年m m m a t t h e w s 和d p s u m n e r 给出下述结果 定理3 2 1 【8 】顶点数不小于3 的n 阶连通的无爪图若6 华，则g 是可迹的 定理3 3 1 【8 顶点数不小于3 的咒阶2 一连通的无爪图若6 孚，则g 是h a m i l t o n 的 1 9 9 1 年d o u 9 1 a l sb a u e r s 等人从邻集并的角度推广了上述两个结论，证明了下 面的结果 定理3 2 2 f 9 】设g 为连通的无爪图若对于任意不相邻的点，“，u ，都有l ( ) u ( t 圳 学，则g 是可迹的 定理3 3 。2 【9 】设g 为2 连通的无爪图：若对于任意不相邻的点t ：。，都有i ( 越) u ( u ) l 鼍产：则g 是h 锄i l t o n 图 对于一般图，陈冠涛得到下列结果 定理3 3 3 【1 0 】设g 是阶为扎3 的2 连通图，如果对任意不相邻的顶点z ，都有 2 i ( z ) u ( y ) i + d ( z ) + d ( 秒) 2 礼一l ，贝0 g 是h 锄i l t o n 图 对于无爪图，李饶得到如下结果，进一步推广了已有的结论。 定理3 2 3 【1 1 】设g 是阶为礼3 的连通无爪图，如果对任意不相邻的顶点z ，y ，都 有2 l ( z ) u ( y ) l + d ( z ) + d ( y ) 2 n 一5 成立，则g 是可迹的 9 山东师范大学硕十学位论文 l o 定理3 3 4 【1 2 】设g 是阶为n 3 的2 。连通无爪图，如果对任意不相邻的顶点z ，y ，都 有2 i ( z ) u ( y ) l + d ( z ) + d ( y ) 2 佗一5 ：则g 是h 锄i l t o n 图 对于连通度为七的无爪图，朱卓宇等又得到下面的定理 定理3 5 1 f 1 4 】设g 是一个阶为咒3 的2 - 连通无爪图连通度为七如果对于每一 个七+ 1 个点的独立集s ，对任意u ：u s 部有i ( u ) u ( u ) i 学，则g 是h a m i l t o n 图 定理3 5 2 【1 5 】设g 是一个阶为咒3 的2 连通无爪图，连通度为七如果对于每 一个七十1 个点的独立集s ，对任意乱，u s 都有i ( u ) u ( u ) i 礼一七一s ，则g 是h a m i l t o n 图 1 9 9 0 年对于3 连通的无爪图，吴正声得到下面的结果： 定理3 4 1 3 9 】 设g 是n 3 阶3 连通的无爪图，若对g 中任意3 个顶点的独立 集 。1 ，z 2 ，z 3 ) ，有d ( z 1 ) + d ( z 2 ) + d ( z 3 ) n + 1 ，则g 是h 锄i l t o n 连通图 1 9 8 2 年r j g o u l d 等得到有关无爪图的下述结果： 定理4 1 【1 8 】g 为直径至多为3 的2 连通的无爪图若g 不含同构于h 的导出子 图，则g 为齐次可迹的 1 9 9 8 年a a i n o u c h e f ；3 5 j 定义了半无爪图并给出了下面的结果： 定理4 2 3 5 直径至多为2 的七一连通( 角2 ) 的半无爪图是哈密顿的 山东师范大学硕士学位论文 第二章( k l ，4 ；2 ) 图的完全圈可扩性 这一章主要研究三角连通条件下( k 1 ，4 ；2 ) 一图的完全圈可扩性 定理2 。4 顶点数不小于3 ，无孤立点，爪心独立的三角连通( k l ，4 ；2 ) 一图是完全 圈可扩的 图1 说明爪心独立”的条件不可去，图2 满足定理2 。4 的条件但不满足定理2 1 条 件 图1图2 以下是定理2 4 的证明 设g 是无孤立点的三角连通爪心独立的( k 1 ，4 ：2 ) 一图由g 无孤立点且三角连 通易知g 的每一个顶点在3 一圈上设c = 饥 2 u 1 为g 的一个圈且i y ( c ) i i y ( g ) 假设c 没有扩圈 记a c = e e ( g ) ：e 仅与y ( c ) 中一点关联) 因为i y ( c ) l i y ( g ) j 且g 连 通，所以a c d 由性质1 知存在3 一圈g ，q ，使得e ( c ) e ( g ) ue ( q ) u ue ( ( ) 且e ( g ) ne ( c ) 国( 1 i m ) v e a c ，由性质1 知存在3 一圈g ，使 得e e ( g ) 且( g ) 中存在g 到g ( 1 i m ) 的最短路为只，令p 为只中长度最 短的路，设其长度为七，尸= 磊磊磊，其中磊= g ，磊 g ，g ，) ：注意 到p 与七依赖于e 的选取，取e a c 及 a ，q ，c 】- 使得七值最小不失一般性假 设磊= g ，由p 的取法可知e ( 五) ne ( c ) = d ( 1 i 七一1 ) 1 1 论断1a c 山东师范人学硕士学位论文 证明若c 1 = c ，则i v ( c ) i = 3 ，而c 磊一1 为c 的扩圈矛盾 由尸的取法知i y ( 疡) ny ( c ) i = 2 不妨设磊= 仳t 。u ，札v ( g ) 一y ( c ) ，z 1 = ：由对称性不妨设v ( + l c 让一1 ) 论断2 + l 一1 证明假设+ 1 = 一1 考虑( 吻，一1 ，+ 1 ，u ) ，可知札一1 ，u 吩+ 1隹e ( g ) ； 考虑( u t ，u 一1 ，u i + 1 ，u ) 可矢口u u i l ，u u i + 1 隹e ( g ) 由于图g 爪心独立所以一1 + l 与忱一1 耽+ 1 至少有一条存在不妨设一1 + l e ( g ) ，则u 仇c b 1 + 1 “为c 的扩圈矛盾 论断3 若一1 + 1 e ( g ) ，则一1 ，+ l 譬e ( g ) 证明假设码一1 e ( g ) 则圈扎c 吻一1 + 1 c 一1 乱为c 的扩圈矛盾 若q + 1 e ( g ) ，则圈钆+ 1 c 一1 + 1 c “为c 的扩圈，矛盾 论断4 ( 1 ) 一l 且u + 1 ；+ 1 且一1 ( 2 ) 艮2 证明( 1 ) 假设= 一1 ，考虑( ：一1 ，+ 1 ，u ，奶一1 ) 乱吩一1 ，u + 1 ，仳忱一1 甓e ( g ) ， 否则得c 的扩圈一l 饥一1 隹e ( g ) 否则得c 的扩圈扎c 一1 一1 虿q 乱一1 + 1 岳 e ( g ) ，否则由论断3 知饥一l 岳e ( g ) ，矛盾这与g 为( k 1 ，4 ；2 ) 一图矛盾忱一1 同 理，+ 1 由对称性知+ 1 ，一1 1 2 ( 2 ) 假设七= 1 e ( z 1 ) ne ( c ) 0 = i 一1 或 = j + 1 与( 1 ) 矛盾 论断5 若口 y ( + 2 c u t 一2 ) ，贝0 乱u ，l岳e ( g ) 证明假设u e ( g ) 令z 7 = 札乱( 或z = u 仇乱) ，路尸7 = z 7 历磊比 路尸= 磊z 1 汤玩短，矛盾 山东师范火学硕士学位论文 论断6 + 2 ，一2 证明假设= 吻+ 2 考虑( ，一1 ，+ 1 ，仇，札) u 吻一1 ，u + 1 隹e ( g ) ，由论断4 知 吻一1 ：q + 1 e ( g ) f e ( ( 吩，一1 ，+ 1 ：耽，u ) ) l 2 ，一l 吻+ l e ( g ) 考虑 圈一1 + 1 吩c 吻一1 ，与论断4 矛盾+ 2 同理让一2 y ( + 3 c 一3 ) 1 。一1 + 1 e ( g ) 否则考虑( ，一l ，+ 1 ，饥u ) u 一1 ，“+ l 譬e ( g ) ，由论 断4 知1 矗i o 一1 ，f 0 + 1 隹e ( g ) i e ( ( t 0 t o 一1 + 1 ，耽，t z ) ) i 2 t 0 1 1 0 + 1 e ( g ) 同理娥一l u 州e ( g ) 2 。吻一1 譬e ( g ) 否则u 一1 乙沁+ 1 吩一1 艺件1 一1 虿u 为c 的扩圈，矛盾 + l 甓e ( g ) ，否则妣0 u 是+ 1 c 一1 + 1 c 一1 + 1 c u & 钍为c 的扩圈，矛盾 3 。仇一1 奶+ 1 至少有一条存在否则考虑( 矾，仇一1 ，饥+ 1 ，札，) u 协一1 ，u + 1 ： 珏移 e ( g )若u h 可i 一1 ，移 i + 1 簪e ( g ) ，贝u e ( ( 秽i ，可i 一1 ，u + 1 ，钍u ) ) l 2 ，矛盾 4 。若t ， 仇+ 1 e ( g ) 考虑( u ，u 一1 ，1 ，_ l l + 1 t o + 1 ，t 0 ) t o t ，_ f l 一1 ，t o t i l + 1 譬e ( g ) 由论 断4 知+ 1 圣e ( g ) 仇+ 1 + 1 隹e ( g ) 否则u 虿+ 1 + 1 c 吩一1 吻+ 1 c 码豇为c 的 扩圈一1 + 1 隹e ( g ) ，否则u u f 瓦_ h + 1 一1 现+ 1 一l 瓦i _ 1 t - u 为c 的扩圈这与g 为( k l ，4 ；2 ) 一图矛盾若忱一1 e ( g ) ：考虑( 一1 + 1 ，仇一1 ，) 一1 ，+ 1 e ( g ) 由论断4 知一1 圣e ( g ) 一1 一1 譬e ( g ) ，否