（应用数学专业论文）若干图类的哈密尔顿性.pdf

独创声明 水人声明所呈交的学位论文是本人在导师指导下进行的研究工作及敢得的研究成 果。掘我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对 木研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 刘睿虏 学位论文作者签名：每j 春岛 导师签字 学位论文版权使用授权书 乙澎 f 小j | 沦文 ：岂j 己仝j ￥堂撞有关保俐、使厂学位沦文的舰定t 有权保雷j 1 l ，r 家仃火滞fjp 奠 j l 句送交论文的复1 = 1 l 件和磁稚允f 1 ：论文被侉间年1 1 供阗。本人援议主 数t i ju 、将：旺沦文的全洲或i i ：分内容编入有关数w 库进行捡索，可以采j 影e ! 、缩 = | 】 ! t k ! l l l l j 等叟捌r 殴f i ：7 i 、j r 绷学他沦文。( 保密m 学他论文征解密后适川4 ：授权。 c ) 刘者房 ；：位论文作者签名：劐畚彦 导师签字 等f j n j ：2 0 0 5 年斗月j 5r 签字刚调：2 0 0 许月胙 些丕堕塑盔鲎塑主堂焦鲨塞 1 若干图类的哈密尔顿性 刘春房 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 本文仅考虑有限、无向、简单图设g 是一个图，v ( g ) ，e ( a ) 分别表示g 的 顶点集和边集 对于f 口l ，啦，口。 cy ( g ) ，用g p h v 2 ，”。 表示由 ”i ，”2 - ， 导出的予 h j 1 1 1 过g 巾每个顶点恰一次的路( 圈) 叫 i ；l m i l t o n 路( 圈) 一t 均为正整数，且2ss i g i ，若g 中任意s 个顶点的导出于图至少含有f 条边，际g 是k t 】图 设f ) = 1 1 1 v 2 w ，是g 的一条( u l ，v r ) 一路，q ，u j 1 7 ( p ) ( i ) 用v i p f i 和 ”，了，分别表示p 的子路 o i v i + 1 和v j , o j l 仉 y ，i7 i ，i7 表示点吨十f 和v i f ，u i u f 表示点v i + 1 仇一1 1 1 i 毗足g 的子图，令n h ，( h 2 ) = v ( h 1 ) j 孔矿( h 2 ) ，使j e ( g ) j 1 ，m ? ( ) 可简记为n ( h ) ，( ( q ) ) 可简记为( u 。) 对f 。cv ( g ) scv ( a ) 及g 的子图，a s 】表示g 中s 的导m 予，也记 为( m ) 表示点z 在g 中的邻点集，吲= g ( x ) u ：r ) n h ( z ) = ( 。) n1 7 ( j 殴。，矿( g ) ，则d y ) 表示。，y 之间的距离，即z 到y 的最短路的长， 没c 魁给定方向的圈，对“，。c , u c ”定义为沿c 的正向从t t 到”连续点 集，反向考虑时定义为”移“ 对i i , ，”c m + 表示c 上沿正向1 的后继点，“+ 表示g 上沿正向i i 的第f 个 后继点，旷，“。可类似定义 山东师范大学硕士学位论文 2 对图g 的两个子图g 1 ，g 2 ，g 1 a g 2 定义为由g 中由e ( g 1 ) u e ( c 2 ) 一( e ( g 1 ) n e ( g 2 ) ) 导出的子图 对于图g ，若任意边c 1 ，e 2 e ( g ) ，g 都有3 一圈序列c l ，q ，a 使得e l ( ，2c - hf ( g ) nf ( g + 】) 0 ( 1si f 一1 ) ，则称g 是三角连通的 符对- t 二任意整数k , 3sr 兰1 l g 存在所有的i 圈，则称g 是泛圈的若对图 中化意点都存在过该点的所有的圈，则称g 是点泛圈的 在本文中，主要得到如下定理 定理2 2 1 设g 是【4 ，2 】图，则 ( 川g 屉连通的当且仅当g 同构于k l , 3 或者g 有h a m i l t o n 路， ( h ) g 是2 一连通的当且仅当g 同构于 2 3 或g 同构于盯1 3 3 或g 有l l a m i l t o t i 吲， 定理2 2 2设g 是9 连通眠2 3 图，则g 同构于2 。l 或g 含有l - b “ 路 定理2 2 3 设g 是“连通【k + 2 ，k 】图，则g 同构于瓦i i v g 或一是l l m n i l l ”n 瞅 定理3 2蹬。为l e ( g ) f 3 三角连通半无爪图，则g 是泛幽的 定理4 2殴c 是【l 阶4 一连通k l 4 一受限图，? 24 2 且t 。s6 6 1 2 ，f ! l jg 乃i h m d l ( j i 、的 关键词： 卜图； 半无爪图；三角连通；泛圈性；k 。t 一受限图 分类号：0 1 5 7 5 坐查竖蕉盔堂堡圭堂垡堡塞3 t h eh a m i t o n i c i t yo fs o m eg r a p h s l i uc h u nf a n g 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 l sr e p u b l i co fc h i n a a b s t r a c t l l g i a p h sc o n s i d e r e di nt h i sp a p e ra r ef i n i t e ，s i m p l ea n du n d i r e c t e d i p r ( ：= ( 1 7 ( g ) e ( g ) ) b eag r a p h ：w h e r e1 7 ( g ) a n de ( g ) d e n o t et h e 、e i “x t 1 ( 1t 、d g es e t ；1 1 ) ds e to fgr e s p e c t i v e l y h l f ，。) 1 ，( g ) ，w el l s eg h ，1 j 2 。1 i od e n o t et h es u b g r | i p hn t l ( 0i s ：a l l e dh a n f i l t o np a t h ( c i r c l e ) i fi tp a s se v e r 3 7 、e r | e xo fgju s t ，l i il i i l t 簧1 p l 、gi sc a l l e d ( s ，t - g r a p h ，i ft h e r ea r ea t l e a s tt e d g e si l le 、t r 、。i n d u c e d h t l fj t ! h 1 p h s 】f + _ 、p l i e x s i 、i ，一i it ! “i sa ( y t u r ) 一p a t h ， 川j i ( ，) ) ( i n w pu s ef ，) r 川j ( i ，l l i t ，t h m o t t h es n l 9 1 a p h 1 il j + 【7 a n dz r 一i ，t ，l r e s p e c t i v f l 、 、t 、1 i h i 、f ，：。，f - i l f ) d e n o t e st h ev e lr e x r ，ic a n df j i f t h l ，f ：t 一【i sf t l ：q t ) d t 、1 1 1 ) i t db y 1 1 1 1 1 2i st h es u b g l a l ho ig l e tn h 。( 凰) _ j 、( h d 3 u i 。( t 1 2 ) i h a f ，cz ? ( g ) i x ：一( ) c a l lb ed e n o t e d1 0n ( 1 f ) s i m p l 3 f - v ( ) ( a t p i l o t “t 【o ( n ) s i i i i i l y i ，1 1 1 i ：c ( g ) sc 、7 ( g ) a m l h i s t ，h es n h g r a p ho f g ，g 【s 】d e n o t e d t h 、i u d u i s u b g la p ho i s a n da s 1c a l lb ed e n o t e dt of s 】s i m p l y ( ，1 ( 1 e n o t e st l i ea d j c e n tv e r t e xs e to fzw h i c hi s i ng 、t 【茁】= a ( 。) un + f f ) 一( t ) nl ( h ) i fh 、( g ) ，d ( ，) i st h ed i s t a n c ei ngf r o mzt oy r w ? ff c k t1 c vd e n o t et h ec o r t s e c u t i v ev e r t i c e so ncf r o mt l m 、i n 汕9 ( 1 i r e e i o l l t 1 1 es a m ev e r t i c e s ，i nr e v e r s eo r d e r ，a r eg i v e nb yu u u ，二” ?nl，一、 山东师范大学硕士学位论文4 i f i so nc ，t h e nt h ep r e d e c e s s o r ，s u c c e s s o r ，n e x tp r e d e e e d d o ra n dn e x ts u c c e s s 1 l 。o f ，a l o n gt h eo l i e n t a t i o no fc a r ed e n o t e db y 杜一? + ，札一一，a n du + + ， e s p e c t i 、，e l y g la n dg 2i st h es u b g r a p ho fg ，g 1a g 2i sd e f i n d e dt ot h es u b g r a p ho fgw h i c h i si n d u ( e d 啷e ( c 1 ) ue ( g 2 ) 一( e ( g 1 ) ne ( g 2 ) ) ag l a p hgi st r i a n g u l a r l yc o n n e c t e di ff o re v e r yp a i ro fe d g e se l ：9 2 e ( g ) 、g h a shs c q u e u d eo f3 - c y c l e sc l ，c 2 ，- ，c is u c ht h a te l c l ，e 2 0 ，a n ds u c ht h a t e ( c ，) ne ( c i + 1 ) 0 ( 1 茎i c 一1 ) ag i a p hgi sp a n c y c l i ci ff o re a c hi n t e g e r ，3 冬k i l - g l ：gh a sat - c j r c l e ； ( ? i s 、e r t e xp a n c 3 7 c t i ci ff o re a c hv e r t e x v ( g ) ，a n df o re a c hi n t e g e r w i t h 3 三； 曼1 1 gh a sak - c y c l ec ks u c ht h a tu v ( c k ) i nt h i sp a p e rw eh a v et h ef o l l o w i n gt h e o r e m s t h e o r e m2 2 1gi sa 【4 2 卜g l a p h ，t h e n 【；1 ) ( ：i s ( ( i i i i c c c di l l g 兰k l ，3o lgh a st i l eh a m i l t o np a t h ( 1j ) ( ：i s2 _ ( o l l u c c l t x li l l g 掣尬3o l g 兰k k l 3o rgh a st h eh a m i l t o nc y c c h 、 p h e o r er n2 2 2gi s2 - c o n n e c t e df 52 1 一g l a p h ：t h e ng 掣2 40 1gh a sh ar n i l t o n p a t h 7 | h e o r e l l l 2 2 3gi sk - ( o n n ( ：t e di k - t - 2 k 卜g l a l ) h f l l f 、l i ( ；曼 t v g o if ：t t a 。； ii l m i i t o i i 、t i e t h e o r e m3 2gi st i i a l l g u l m l yc o m m c t e dq a u s i c i l w f l e eg l 。a p h ，a n di e ( g ) l ： 1 1 1 ( 1 1gi sp a n e 3 c l i c ， t h e o r e m4 2gi sa4 - c o n t l e c t e dk i 4 一? e s t 7 i c t e dg r a p ho f0 1 c h ，il l t 1 2 i 【l ，7 ( j f i】2 t , h e nc ：i sl m m i l t o n i a u k e yw o r d s ：卧卜g r a p h ；q u a s i c l a w f r e eg r a p h ；t r i a n g u l a , 1 3 c o n l i ( * ( i e d ：1 ) a l l ( ：5 y l i c 、i i，r s h i c t e dg r a p h c l a s 8 i f c a t i o n ：0 1 5 7 5 山东师范大学硕士学位论文 第一章引言攻预备知识 5 1 1 引言 5 h a m i l t o n 问题是图论中很重要的一个问题一百多年前，爱尔兰数学家哈密 儿顿提出了这样一个问题：一个连通图有h a m i l t o n 圈的充分必要条件是什座但 足这个问题至今未能解决，后来人们发现它是个n p c 问题，于是对它降低要求间 接研究这个问题其中一种思路就是研究某些特殊图类 曾经一段时间以来，无爪图h a m i l t o n 问题的研究被许多人士所青昧，对该问 题的结果相当多，可是几乎已经到了山穷水尽的地步了之后，一些学者对无爪图 作j ，定的推广，研究一种和无爪图很类似的图类，这就是人们所共知的。爱 限，虽然该种图类也已经广泛被研究，但是基于对某些条件的改进，kt 受限 h1 l m u i h 0 1 1 问题的研究一直没有结束，本文就是在这种情况下，作了有关“t 受 限i l l 0 1 1 问题的结果 时，本文综合多种思路又研究了其他两类特殊图类的有关问题其中一类矗 卜i1 一1 勺1 1 1 1 i il o u 性问题，这是一种新定义的图类；另一类是q u a s i c l a _ 、x m 蚓 的泛问题这些都是比较有意义的问题 山东师范大学硕士学位论文 1 2预备知识 6 本文仪考虑有限、无向、简单图，所用的记号和术语约定如下，其中未加说明 的部分请参照文献f 1 1 设g = ( 叫g ) ，e ( g ) ) 是一个图，v ( g ) ，e ( g ) 分别表示g 的顶点集和边 集 i g = i v ( c 对于( l ，”2 ， v ( g ) ，用g 扣1 ，陋“ 表示由 h u 2 ，。 导出的子图通过g 中每个顶点恰一次的路( 囤) 叫h a m i l t o n 路 ( 同) 州均为正整数，且2ss l c l ，若g 中任意s 个顶点的导出子图至少含 有l 条边，称g 是【s ，t 卜图设p = v l v 2 是g 的一条( 口i ：b ) 一路，：c j 1 ( p ) ( i j ) ，用v i p v j 和v i p v i 分别表示p 的子路t n n + l f7 和r7z 7 1 o 。 f ，。7 f ，i “表示点+ f 和 一， ，v ：- 表示点巩+ l ，y i _ 1 日l ，王如是g 的子图，令 v ，( h 2 ) = ，i7 ( h i ) lj u 1 ( ) ，使札u e ( g ) ) 其中( h ) 可简记为 ( ，】，、( “ ) 可简记为n ( v i ) 刈j ：，( - l ( “) s ( 1 + ( g ) 及g 的子图h g 【s 1 表示f ；中s 的导f j 子吲，也i 己 为1 5 i ( 。) 表示点f 在g 中的邻点集，n = n ( c ) u 协 v h ( r 户a ( ，+ ) n 1 ( ，j 没 “( - 1 ( g ) ：则r m j ，) 表示，y 之间的距离，即z 到9 的最短路的长没r 足给定力1 勺圈，对玑 c ，u c v 定义为沿c 的正向从 t l 到f 连续点集，反向考 虑时j t 义为t p ，对mu ct ，表示g 上沿正向“的后继点，u + 2 表示( 。上沿 l 州，j ，的第j 个岳继点，y f 一，n “可类似定义对图c 晌两个子图a 1 ( j 2 f “c ! ；蕾义为1 l i ( ? 1 i 1f ( g i ) uf ( g 2 ) 一( e ( gl ) nf ( g 2 ) ) 导f 】 的了【引， 刘j ：图( 7 若任意边c - ，( 2 2 z ( c ) ，g 都有3 一圈序列c 1 o c j 陵0 q ( ( 1 i f ：2 ce ，且s ( c 。) ne ( c i + 1 ) 0 ( 1si 曼f 1 ) ，9 l l j 称g 是三角连通的 c ；( 一) 是满足如下要求的图：以图g 中所有3 一圈为点集，两个点c 1 g 之间有边 当且仅当g 。( 之在g 中有公共边三角连通图具有如下性质： 性质1 1 t 3 ：连通，局部连通图是三角连通的 性质1 2 弛幽( ? 是三角连通的当且仅当 ( i ) vr ( 二e ( g ) ，j g 、( c 3 ( g ) ) 使得e e ( e ) ( i i ) c 3 ( ( ? ) 是连通的 若对于任意整数，3 a v c i ，g 存在所有的 圈，则称g 是泛圈的若对 卧f 任意一点都存在过该点的所有的七圈，则称g 是点泛圈的， 称一个图g 为半无爪图，如果它满足下面的性质：d ( z ，v ) = 2 = 等存在 i ，n ( 彳) n n ( v ) 使得n u 】 z u n m 若d ( m ，p ) = 2 ，i ) i j i 己j ( z ，) = “ - 、7 ( _ ) nn ( ) i n i x 】u n m 所以若g 为半无爪图，则对任意距离为2 的点 山东师范大学硕士学位论文 7 _ ，必有j ( x ，) d 易见无爪图包含于半无爪图a i n o u c h e 2 1 最早提出了半无 爪图的概念，并把一系列的关于无爪图的哈密顿性结果推广到半无爪图，证明了下 面定理 定理1 3 吲若g 是连通局部连通半无爪图，则g 是泛圈的 赖宏建h 提出了三角连通的概念，并且证明了下面关于无爪图的结果 定理1 4 设g 是三角连通无爪图，l e ( a ) i 3 时g 是点泛圈的 一个图g 称为1 i ，一受限图，如果图g 中的任意一个p 一爪中1 度顶点集合 的导出子图中至少含p 一2 条边特别地当p = 3 时k - 受限图即为无爪图 一个图g 称为k - r 受限图，如果图g 中的任意一个4 一爪中1 度顶点集合 的导出子图中至少含两条边 山东师范大学硕士学位论文8 第三章【s ，t 卜图的h a m i l t o n 性 征这一章中，我们主要讨论了 s ，t 1 - 图。在21 中主要介绍了【s ，t 】图的概念 并给出了关于 s ，t 】- 图的性质及有关引理；在52 2 中我们给出了本章的主要定理 及其证明，并对定理2 22 进行了图例说明，给出了定理条件的不可降低性 2 1有关【s ，t 】_ 图及其性质 本节主要介绍了【s ，t 卜图的概念并给出了f s ，t 卜图的性质和一个重要引理 s , t 均为正整数，且2 8si g l ，若g 中任意s 个顶点的导出子图至少含有t 条边，称g 是f s t 】- 图 通过g 中每个顶点恰一次的路( 圈) 叫h a m i l t o n 路( 圈) ， 下而的。陀质1 和性质2 是显然的， 性质2 1 1k t 卜图必是( h t l 卜图 性质2 1 2 卜卜图必是i s + 1 ，卜图 性质2 1 3h t 卜图必是【s + l ，+ 1 一图 证明：没g 是【s ：f 卜图，但不是p 十1 ，+ l 卜图，则存在8 + 1 个点，其 i r - z t t - 图含：仃至多f 条边，记这s + 1 个点为。l ，z 2 ，z 。+ i ，则存在一点、o ，使z 。 + 了r 1 ，一o + 1 n + ，中的点有边相连，否则，与g 为f s ，f 一图矛盾。不妨设 ，一t 1 ，考虑罔g h z 2 ，z 。l ，则i g h u 2 ，- w 。】| ，一l 与k t 卜_ 矛盾口 引理2 1 4 没p = hc 屯u 。是连通图g 的最长路，是gp 的卟分 支，一( j v f ，( ，) 则 ) ( 一) l j 、( 。岛) r ( p ) ； ( 1 ，f ，+ z - 、) ( h ) ；c t v q ，u i u ， o q u f 仨e ( g ) ( t o 若又有f 1 ，v r ( ) ( i 7 ) ：则 _ u i ， j ；u i ，i ! 1 1 1 t e ( c ) 证明甭u ! 易得长于p 的路 口 山东师范大学硕士学位论文9 5 2 2 有关 s ，t 卜图及其性质 本节在2 1 的基础上，给出了几个定理的证明，并对第二个定理进行了图例 说明，说明了定理“2 一连通”条件是不可降低的；第三个定理在前两个定理的基 硎 上给出了一般性的结论 下而的定理是本文要证明的主要结果 定理2 2 1 设g 是f 4 ，2 _ 图，则 ( a ) c 是连通的当且仅当g 同构于甄3 或者g 有h a m i l t o n 路 ( h ) g 是2 一连通的当且仅当g 同构于施，3 或g 同构于k l ，l 、3 或g 有h a m i l t o n 圈 证明( a ) 只需证明，如果g 不含h a m i l t o n 路，则g 同构于k 1 3 即可令 q t 。以，是g 的一条最长路，则g23 ：下设l p l g l 由连通性及引理可 钾i ，行：z tf ，i ( g ) 一i ( p ) ， u i v ( p ) 一 l ，w q ，使1 w 。e ( g ) 若u 。h r 由 引理即得，1 6 ( g 陬，”。，u ，u f 】) l 1 ，与g 是 4 ，2 卜图矛盾因此必有= 对 硝：地可以证得 u f = u 彳于是p = m v 2 v 3 若v ( g ) v ( p ) 一 t 也因为g 连通， 所以存在t j 17 ( g ) 一( u l ，2 1 2 ， u 3 ，t t ) ，由p 的最长性及引理考虑c v h y1 可知 ( g hhf r j ) l = 0 矛盾于g 是 4 2 卜图所以l ( g ) = 1 r ( p ) l 9 “ ，可见g l ：黝】：。 ( 充分性显然下面证明其必要性设g 不同构于b 。和凡lh ，取“的最 k 陶r 若e 不是h a m i l t o n 圈，设h 是g e 的个分支若i 肮? ( h ) 3 ， u ry ： 0 ( h ) 及t ，h ) ，注意到g 最长，易得l e ( g 卜， ，。+ ) 1 = 0 矛孵于g 是h 2 卜图因此i c ( h ) i 茎2 ，而g 是2 连通的，所以i ( ，) 1 2 i 殳1 、j ( ，) f = = 。 岔口果l z + c 一 = ! ，+ c x 一 = 1 觋4l f = 4 此时( ；一( = “j 然， f ? r 有另一个分支hl ( ) ，则。：，( ( h i ) ，j j ；= 实上：特有w re ，? l f j ) ( e ：i ( i ) ) ，考虑g w ，u ，l + ，：j ：- - ( u 1 7 ( h ) ) 有“，l 上：j 一j 一 f ( g ) 与g 是 4 ，2 _ 图矛盾所以zg c ( h - ) 类似可证掣杖? ( ，)但 址2 一连通知i ( h i ) l 2 ，故只有g ( h 1 ) = z 一+ ) ，得长于r 的圈， 矛盾。所以，g c = h 而只有1 h l = 1 否则取l ，u 2 v ( 爿) ，考虑 r ? h i i - 2l j 一，+ ，有矿+ ，“l 一，u t y + ，t 1 2 z + ，u 2 + 垡e ( g ) ( 否则易得长于c 的圈) ， 所以i ( g h ， u 2 ，z + ，可+ ) 1s1 ，与g 是【4 ，2 】_ 图矛盾考虑c y 一，y + 丁+ ：u 】( “ 1 ( ) ) 易见u y 一，u y + ，x + y + ，u 矿ge ( g ) 由g 是【4 ，2 ) 1 - 图可知y - y + e ( g ) 考 虑g p 一，矿，y 一，u ，类似地可得z 一。+ e ( g ) 可见l 可+ c x i 3 ( 若l 旷c x i 2 ， 易得k 于e 的圈) 设y 一在旷c x 一上的最后一个邻点为z ，则z z 一，z q ( 否则可 山东师范大学硕士学位论文 1 0 得长于c 的圈) 考虑g 扛+ ，管一，矿，u ，有u 矿，u y 一，u z + ，9 一矿，茁+ z + e ( g ) 与 g 是f 4 2 _ 图矛盾此矛盾说明定理2 2 1 b ) 成立 口 定理2 2 2 设g 是2 连通【5 ，2 卜图，则g 同构于虬，4 或g 含有h a m i h o n 路 证明如果g 不含h a m i l t o n 路，取g 的一条最长路p = n t 2 t 口，设 是g p 的一个分支，u y ( h ) 由g 的2 一连通性及引理可知，存在 t “p ( 日) ( 1 i j q ) ，且j i + 1 如果 ，口i ，由引理可得l e ( c b ， 。，：u 产，”于，】) l 1 ，矛盾于g 是一2 1 - 罔。此矛盾说明c o = 丁对称的可证得：仇= t ， 如果i v ( t 寸p t ，) i 2 可得 i e ( g ht k 。， ，；u i ) 1 1 ：得矛盾故必有l v ( u p u 7 ) 1 = 1 ，即p = v l v - 2 7 1 ：i c 一 汴j 震i 至u v ( c 。) un ( z 。) 1 7 ( p ) ，及l n ( v 1 ) 【2 ，1 、r ( ”f ) l 2 ，又y ，f j ，”j 彰r ( g j 所以只有v l t j 4 ， 0 2 如e ( g ) 如果v ( g ) 7 ( p ) u ( ) ，则存在 t o v ( g ) 一y ( p ) u 1 ) ，考虑g u ，u ，口3 ：岛1 “，掣e ( c ) ( 否则易得长于p 的路) ，再结合引理，知i e ( g h w ，t 1 沁i ) i 1 抖矛盾所以i ( 一) = 1 。( p ) l j t ，) ，并目由上述i j l ：_ u j l 可见g 同构予 i 定理2 ! 2 证毕，口 需要说l 啊的是，下面的图1 是一个不含h a m i l t o u 路连通1 1 一图，同时该匪1 还说l jj 定理2 2 2 中的“2 一连通”条件是不可降低的；图2 是一个不含h a m i h f ) l l 罔的! 一连通【4 ，l 卜图；图3 是一个不含h a m i l t o n 路2 一连通h 1 卜图 刚1 定理2 2 3 设g 是k 一连通【k + 2 ，叫一图，则g 同构于耳鬲v g k 或g 是 i t a m i l t o n 圈 证明如果g 满足定理条件，但不是h a m i l t o n 圈令c 为g 的最长圈，则 g c 0 山东师范大学硕士学位论文 论断1g c 的连通分支都只能有一个点 证明否则，设日是g c 的一个连通分支，且l h i 2 ，则由g 的k 连 通性知( ) k ，令 。1 ，v 2 ，仇) = w c ( h ) ( t k ) ，由i h i 2 ，必然存在 3 ；t t 2 h ，使n ( x 1 ) n l ，7 ) 2 ，仇) o ，扛2 ) n u l ， 2 ，u 矗0 ，否则若只有 1 1 h 满足n ( z ) n ”t ，u 2 ，仇) d ，则g z ) 不连通，矛盾 这样，考虑g p 产，u 手， ，2 l ，3 ；2 ，只可能有f r l 2 一条边，矛盾于g 是一 连通限 2 ”一图 论断2g c 只有一个连通分支 证明设g c 有两个连通分支g z 1 ，g x 2 ，令 ，现， c * 小：) 则 考虑 g i t 彳、w 手，- 一u 毒，3 3 1 ，轨】，x 2 与” ，”手，”声中至多一个点相邻，矛盾于g 足| _ ! ”，图 l 、而令g 一( 。= n ) ，c ( 。) = ( 口i ，地，：一，u f 当t + l 时，考虑 g h ，。五一。毒u + ，。】，矛盾于g 是f + 2 ，纠一图 再考虑t = k 的情形，此时分两种情形讨论： 情形l 当1 r o t ，i i = 1 t ，；。c v g 一= i ” c u 彳l = l 时 此刚。g 只有l j ，y ，2 一，巩， ， 手j ， 声z ，z 共有2 七+ 1 个点 其- h r 嵋。一t 1 毒，z 独立由 一连通性知，t l + 与。，一r 。椰棚 h ，f i jy i ，。2 - 一? 者| 5 相令$ ， 声与fj 【，y ，2 1 者| ；抖1 5 7 - 1 f ! i 之f lj j i j j 边疗扯与否征意 这样，g 同构与瓦v g k 情形2 若存在某一i 便i 产e u 五。 22 则 考虑g ， 寸，z l i ，z 】，由于g 是陋+ 2 ，叫一图，所以c - 。与r t ，” 一，j 邮州邻 山 ：r j 十l 与，0 l 相邻，与t ，4 2 不相邻，故在。t 浮l c l 2 上存在一点z - 是苹一 个与6 i 一_ f ，不相穹f ；自0 点 考虑g 【 j ，t 。j ，一，u ， 4 i ，w + ，w 亭，m 】， 若c + f j ，j ( g ) ，贝4z u 虿u 十 g u 彳u 刁啦z 长于g 同理可证，r 与。，口手，“_ i 卜，u 喜2 ，- ，可寸不相邻 这弹，：l 可能有边u 本。与u ， 手，u ，”茸一，u 矛盾于g 是【k + 2 ，纠一图 定理2 2 3 证毕 口 堂丕堕薹盍堂亟主堂焦堡塞 1 2 第三章q u a s i c l a w f r e e 图的泛圈性 1 9 9 6 年，a a i n o u c h e 对q u a s i c l a w f r e e 图的h a m i l t o n 性问题作了系列研 究，作出了如下结果：阶大于等于3 的连通，局部连通q u a s i c l a w f r e e 图是泛圈 的 而李饶于最近几年也对q u a s i c l a w f r e e 图作出了相关结果，2 0 0 1 年他对3 一连 通q u a s i c l a f r e e 图做了研究，2 0 0 2 年对2 一连通q u a s i c l a w f r e e 图傲了研究，分 别给出了很好的结果，许多学者对q u a s i - c l a w f r e e 图的热衷，说明了q u a s i c l a w f i e e l 蓦的研究具有很重要的意义 本章的结果是对a a i n o u c h e 所做结果的一种改进 3 1概念、性质及相关定理 对于图g ，若任意边e ，e 2 e ( g ) ，g 都有3 一圈序列c 1 岛，a 使得 ( d l ，p 2 0 ，且e ( g ) ne ( g + 1 ) d ( 1 i 曼f 一1 ) ，则称g 是三角连通的 c ；( f ? ) 是浦足如下要求的图：以图g 中所有3 一圈为点集，两个点c ，之问有边 当z 当a c t 在g 中有公共边三角连通图具有如下性质： 性质3 1 。1 t 连通，局部连通图是三角连通的。 性质3 1 2 1 1 】：图g 是三角连通的当且仅当 ( i ) v pc - - e ( c ) ，三| e 17 ( c 3 ( g ) ) 使得e e ( g ) ( i i ) c ： ( g ) 是连通的 若对。r f 王意整数k , 3 曼 ：曼1 、台i ，g 存在所有的 圈，则称g 是泛斟的若对 h 【懑i i - r ，存在过该点的所有的 圈，9 川称( 7 是点泛矧的 称一个图g 为半无爪图，如果它满足下面的性质：( f ( n j = 2 存在 c ，( ：、f ( 一) n n ( y ) 使得n u 】【z 】u n v 1 若d ( z ，) = 2 ，则记j ( x ：u ) = “ 、( ，) n 、t ( ) | n z 】un m 所以若g 为半无爪图，则对任意距离为2 的点 r 小必育，( 1 ，) o 易见无爪图包含于半无爪图a i n o u c h e 2 1 最早提出了半无 爪的慨念，并把一系列的关于无爪图的哈密顿性结果推广g , j - - t a 无爪图，证明了l j 而定理 定理3 1 3 h 若g 是连通局部连通半无爪图，则g 是泛圈的 赖宏建川提出了三角连通的概念，并且证明了下面关于无爪