（应用数学专业论文）禁用子图与图的hamilton问题.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 ( 注：如没有其他需要特别声 蝴的本栏可空) 或其他教育机构的学位或证书使用过的材料。与我同工作的同志对 小研究所做的任何贡献均己在论文中作了明确的晚明并表示谢意。 学位论文作者签名：越逸霞 ， 铷签字：删 学位论文版权使用授权书 小川置沧文作哲壳全了解堂撞有关保留、使用学位论文的规定，有权保尉并向 京t t 父闭j 或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权兰 数j 以：l 孑学他沦文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 二r k i 十i i i 譬复制下段保存、汇编学位论文。( 保密的学位论文在解密后适辟| 本投杈粥) 州立论文作者签名：趣诲霞 导师签字 铃t ，：i 则：2 0 0 年牛月f 工同签字同期：2 0 0 土年彳月f 明 禁用子图与图的h a m i i t o n 问题 赵海霞 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 摘要 路和圈是图的两个基本结构，是分析、刻画图的结构的有力工具，有大量的实 际问题可蹦归结为图的路和圈的问题图论中三大著名难题之一的h a m i l t o n 问题 本质上也是图的路和圈问题图的路和圈的研究一直是图论中的热点研究领域最 近若干年，这方面的研究主要集中在图的h a m i l t o n 性、泛圈、点泛圈、圈可扩、 h a m i l t o n 连通、泛连通、路可扩、最长路、最长圈等性质的研究上，而且已经取得了 长足的发展由于直接研究任一图类h a m i l t o n 问题往往比较困难，于是人们转而 研究不含有某些禁用子图的图类，如无爪图，几乎无爪图，拟无爪图等1 9 9 7 年， z d e n e kr y j d s e k 在【4 1 中提出了一种新的闭包概念并证明了无爪图的h a m i l t o n 性 是闭包下的稳定性质1 9 9 9 年，b d l ab o l l o d s ，z d e n d kr a 洗 e t a l 在【6 中提出 了，闭包的概念，并证明了无爪图的一些h a m i l t o n 问题的稳定性和不稳定性至 今，关于无爪图的闭包和h a m i l t o n 问题已经有很多很好的结果本篇论文中定义 了一种新的图类( k l , p ；g ) 一图主要目的是把无爪图的一些性质结论推广到( k ：q ) 一 图本文中主要研究( k 1 4 ；2 ) 图的一些h a m i l t o n 问题 在第一章中，主要介绍了文章中所涉及的一些概念、术语符号和本文的研究背 景以及已有的结果 在第二章中，给出了( k 切；q ) 一图的简单却十分重要的性质及推论，即 定理2 1 ( k 1 ，p ；g ) 一图必为( k l 卅l ；q4 - 1 ) 图 推论2 2 设t 是不小于l 的整数，则( kl ，；口) - 图必为( k l , p + t ；q + t ) 一图 在第三章中，弓i 入了一闭包的概念及相关结论对于无爪图g ，c l k ( g ) 是唯一 确定的并且保持了图的许多h a m i l t o n 性质，成为研究无爪图的强而有力的工具 令口是一个图类，如果对于口中任意的图g ，c l k ( g ) 口，则称口是k 一闭包下的稳定 图类令秽是k 闭包下的稳定图类，对于毋中任一图g ，若g 有性质当且仅当 c l 女( g ) 有性质，则称性质为k 闭包下的稳定性质对m 一连通无爪图，r y j d s e k 等人提出了闭包的概念并证明了以下的结论： 定理3 1 4 】若g 为无爪图，则( 1 ) c f ( g ) 是唯一确定的；( 2 ) c ( g ) = c ( c j ( g ) ) 推论3 2 1 4 若g 为无爪图，则g 为h a m i l t o n 图当且仅当c l ( a ) 为h a m i l t o n 些奎塑塾丕兰堡主堂焦鎏塞2 图 定理33 f 5 若g 为无爪图，则p ( a ) ：p ( c j ( g ) ) 推论3 驴l 若g 为无爪图，则g 可迹当且仅当c z ( c ) 可迹 定理3 5 15 】对任意整数n 1 4 ，存在n 阶的2 连通无爪图g 使得c f ( g ) 为齐 次可迹的，但g 不是齐次可迹的 定理3 6 1 剐对任意整数”t 2 ，存在m 连通无爪图g 使得c ( g ) 为泛圈的，但 g 不是泛圈的 定理3 。7 f 5 】对任意整数m 22 ，存在m - 连通无爪图g 使得e l ( g ) 为点泛圈的， 但g 不是点泛圈的 定理38 i 5 l 对任意整数m 2 ，存在m 连通无爪图g 使得c t ( g ) 为圈可扩的， 但g 不是圈可扩的 因此可知周长，最长路长是闭包下的稳定性质对m 连通无爪图，当m22 时，泛圈，点泛圈，圈可扩都不是闭包下的稳定性质，对无爪图，存在无穷多的图 g 满足d ( g ) 为h a m i l t o n 连通的，但是g 不是h a m i l t o n 连通的可见h o t ，d l t o t t 连通与齐次可迹也不是闭包下的稳定性质为了解决这一问题，1 9 9 9 年b o l l o b 6 , s 等人对闭包这概念做了推广，提出了k 一闭包的概念并证明： 定理39 6 若g 为无爪图，则 ( 1 ) 对任意的，c c k ( g ) 是唯一确定的； ( 2 ) g 是h a m i l t o n 连通的当且仅当d 3 ( g ) 是h a m i l t o n 连通的； ( 3 ) 3g 是齐次可迹的当且仅当c 1 2 ( g ) 是齐次可迹的 因此h a m i l t o n 连通和齐次可迹分别为c f 3 ( g ) 和c 1 2 g ) 下的稳定性质在第三 章中主要研究( k 1 , 4 ；2 ) 图在闭包下的稳定性质因为( k 1 , 4 ；2 ) ，图包含无爪图，所 以对无爪图在k 闭包下不稳定的性质，对( k 1 , 4 ；2 ) 图仍然不稳定因此，我们只 讨论无爪图在k 闭包下稳定的性质本章分为四节，第一节研究( k l “2 ) 一图的闭 包的两个性质，我们证明了： 定理31 0设g 是乃一，r e e 或k 【v 只1 r e e 的( k ；2 一图，则c f ( g ) 仍为 ( k 1 , 4 ；2 ) 一图， 定理3l l 设g 是死- l r e e 或k lvp 4 一f r e e 的( k 1 4 ；2 ) 一图，则c f ( g ) 是唯一确 定的 第二节中证明了： 定理3 1 2 设g 是t 3 一， e 或k lvp 4 一，r e e 的( k 1 ，4 ；2 ) 图，则e ( o ) = e t e t ( a ) ) 推论3 1 3 设g 是b 一，r e e 或k lv b f r e e 的( j ，4 ；2 ) 一图，则g 为h a m i l t o n 图当且仅当c ! ( g ) 为h a m i l t o n 图 些奎堕塾盔堂塑主兰垡鲨塞 3 并证明了定理中“一，r e e 或k l v p 4 - f r e e ”这一条件不可去掉且当g 是码 ，r e e 的( k 1 , 4 ；2 ) - 图时定理3 1 2 是定理3 1 的推广当g 是k 1vp 4 一，r e e 的( k 1 , 4 ；2 ) 一 图时，给出了无穷多个满足定理3 1 2 但不满足定理3 1 条件的图第三节中证明： 定理3 1 4 设g 是死，r e e 或甄v p 4 一f r e e 的( k 1 4 ；2 ) 图，则p ( g ) = p ( c 2 ( g ) ) 推论3 ，1 5 设g 是t 3 一，r e e 或k l vp 4 一，r e e 的( n ，4 ；2 ) 一图，则g 可迹当且仅 当d ( g ) 可迹 并证明了定理中“t 3 一f r e e 或k lv 只一f r e e ”这条件不可去掉且当g 是t 3 f r e e 的( k 1 , 4 ；2 ) 图时定理3 1 4 是定理3 3 的推广当g 是】vp 4 一，r e e 的( k 1 ，d ：2 ) “ 图时，给出了无穷多个满足定理3 1 4 但不满足定理3 3 条件的图第四节中证明： 定理3 1 6 设g 是 孔，耳l vp 5 ) 一，r e e 或k l vp 4 - ，r e e 的( k 1 ，4 ；2 ) 一图，则g 是 h a m i l t o n 连通的当且仅当d 3 ( g ) 是h a m i l t o n 连通的 易见当g 是 死，k l vp 5 ) 一打e e 的( k j ，4 ；2 ) 一图时定理3 】5 是定理3 9 的推广 当g 是lvp 4 f r e e 的( l ，4 ；2 ) 一图时，给出了无穷多个满足定理3 1 6 但不满足定 理3 9 条件的图 在第四章中研究连通，2 局部连通的( k i ，4 ；2 ) 一图的h a m i l t o n 性，我们证明 了定理4 , 2 ，并给出了定理4 2 所能解决但是定理4 1 不能够解决的图 定理41 【7 】若g 为连通，2 一局部连通，6 2 的无爪图，如果g 中不舍有 同构于g l 或g 2 的导出子图h ，满足h 中的4 度顶点在g 中不是局部连通的，则 g 为h a m i l t o n 图 定理4 2 设g 是连通，2 局部连通，6 6 的( k 1 小2 ) - 图，如果g 中不含 有同构于g l ，g 2 或g 3 的导出子图h ，则g 为h a m i l t o n 图 关键词：【k 1 ，；g ) 图； 局部一连通；m - 局部连通； 闭包 分类号：0 1 5 7 出壅堕蕉盔堂亟堂焦迨塞4 f o r b i d d e ns u b g r a p ha n dh a m i l t o np r o b l e mo fg r a p h s z h a oh a i x i a 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 h a m i l t o np r o b l e mi so n eo ff u n d a m e n t a lp r o b l e m si ng r a p ht h e o r y t h ef o l l o w i n g a s p e c t sa r em a i n l yf o c u s e do n ：c y c l ep r o b l e ma n dp a t hp r o b l e m i nd e t a i l ，t h e r ea r em a n y p r o b l e m so fh a m i l t o nc y c l e ，p a n c y c l i c i t y ，v e r t e xp a n c y c l i c i t y ，c y c l ee x t e n s i b i l i t y h a m i l t o n c o n n e c t e d ，l o n g e s tp a t h ，l o n g e s tc y c l ee t c b u tu s u a l l y i t i sd i f f c u l tt ow o r ko u tt h e h a m i l t o np r o b l e mo fa n yg r a p h ，t h e nw et u r nt oe x p l o r et h eg r a p h sn o tc o n t a i n i n gf o r - b i d d e ns u b g r a p h ，f o re x a m p l e ，c l a w - f e eg r a p h ，a l m o s tc l o l o f c e eg r a p h q u a s ic l a w 。f r e e g r a p hw h i l ei nt h i sp a p e r ，an e wc l a s so f g r a p h si sd e f i n d e d i ti sc a l l e d ( 耳i p ：q ) 一g r a p h w e m a i n l yd i s c u s st h er e l a t e dh a m i l t o np r o b l e mo f ( k l ，4 ；2 ) 一g r a p h sw h i c hc o n t a i nc l a w 一，7 e e g r a p h s i nt h ef i r s tc h a p t e r ，w eg i v eab r i e fi n t r o d u c t i o na b o u tt h eh a s i cc o n c e p t s ，t e r m i n o l o g i e sa n ds y m b o l sw h i c ha r eu s e di nt h i sp a p e ra n dr e s e a r c hb a c k g r o u n dw i t hs o n i c k n o w nr e s u l t , s i nt h es e c o n dc h a p t e r ，w ep r o v ea ni m p o r t a n tr e s u l to f ( k l ，p ：o ) 一g r a p h ，t h a t i s ： t h e o r e m2l e v e r y ( k t ，p ；q ) 一g r a p hi sa ( k 1 p i ；q + 1 ) 一g r a p h c o r o l l a r y2 2 l e tt 1b ea 1 1i n t e g e rt h e ne v e r y ( k l ，p ；q ) - g r a p hi sa ( k i p 一；q + f ) g r a p h i2 】t h el l | 1 dc h a p t e r ，w ei n t r o d u c et h ec o n c e p t so fk - c l o s u r ea n ds o l n er e s u l t sa b o u ti t f o rc l a w f te eg r a p h g l c l ( o ) i s w e l l d e f i n d e da n dk e e p m a n y p r o p e r t i c so f h a m i l t o n i c i t y l e t 口b eac l a s so fg r a p hw es a yt h a tt h ec l a s sdi ss t a b l eu n d e rt h ec l o s u r e ( 0 2 s i m p l y s t a b l e ) i fc f ( g ) 口f o re v e r yg 秽l e t 毋b eas t a b l ec l a s sa n dl e t b eap r o p e r t y w e s a yt h a tt h ep r o p e r t y i ss t a b l eu n d e rt h ec l o s u r e ( o rs i m p l ys t a b l e ) i n t h ec l a s s0i f g 0h a sfi fa n do n l yi fc l k ( g ) h a s f o rm c o n n e c t e dc l a w - f l e eg r a p h ，r y j d e ke t a l d e f i n e dt h ec o n c e p t so fc l o s u r ea n dp r o v e dt h ef o l l o w i n gt h e o r e m ： t h e o r e m3 1 4 1l e tgb eac l a w f r e eg r a p h t h e n ( 1 ) t h ec l o s u r ec t ( g ) i sw e l l d e f i n e d ；( 2 ) c ( a ) = c ( d ( g ) ) c o r o l l a r y32 【4 】l e tgb eac l a w f r e eg r a p h t h e ng i sh a m i l t o n i a ni fa n do n l y i fe f ( g ) j sh a m i l t o n i a n 些丕竖堇盔堂堡主兰焦垒塞 t h e o r e m3 - 3 p ll e tgb eac l a w f r e eg r a p h t h e np ( a ) = p ( c f ( g ) ) c o r o l l a r y34 【5 j l e tgb eac l a w f r e eg r a p ht h e ngi st r a c e a b l ei fa n do n l vi f e l ( o ) i st r a c e a b l e t h e o r e m3 5 【5 jf o ra n yn 1 4 ，t h e r ei sa2 - c o n n e c t e dc l a w f r e eg r a p ho nnv e r t i c e s s u c ht h a tc l ( o ) i sh o m o g e n o u s l yt r a c e a b l e ，w h i l egi sn o th o m o g e n o u s l yt r a c e a b l e t h e o r e m3 6 悼l p e re v e r ym 22 , t h e r ee x i s t sam c o n n e c t e dc l a w f r e eg r a p hg s u c ht h a tc l ( g ) i sp a n c y c l i c ，w h i l egi sn o tp a n c y c f i c t h e o r e m3 7 h f o re v e r ym 2 ，t h e r ee x i s t sam c o n n e c t e dc l a w f r e eg r a p hg s u c ht h a td ( a ) i sv e r t e xp a n c y c l i c ，w h i l egi sn o tv e r t e xp a n c y c l i c t h e o r e m3 ，8 1 5 f o re v e r ym 2 ，t h e r ee x i s t sam - c o n n e c t e dc l a w f r e eg r a p hg s u c ht h a te l ( a ) i sc y c l ee x t e n d a b l e ，w h i l egi sn o tc y c l ee x t e n d a b l e w ek n o wt h a tt h ec i r c u m f e r e n c ea n dt h el e n g t ho ft h el o n g e s tp a t ha r es t a b l ep r o p e l t i e sf o rr n - c o n n e c t e dc l a w f r e eg r a p h s ，t h ep r o p e r t i e so f p “n c 可c c z c t ，v e r t e xp a n c y c l i c i t y a n dc y c l ee t e n s i b i l i t ya r en o ts t a b l ef o ra n y7 n f o rc l a w ，f e e g r a p h ，h a m i l t o n i a n c o n n e c t e d a n dh o r n o g e n o u s l yt r a c e a b l ea r ea l s on o ts t a b l e i n1 9 9 8 b o l t o b d se t a ld o f i n e dan e wc l o s u r ee l k ( g ) ( k 1 ) a sag e n e r a l i z a t i o no fc l ( g ) a n dp r o v e dt h ef o l l o w i n g t h e o r e m t h e o r e m3 9 6 1l e tgb eac l a w 一，eg r a p ht h e n ( 1 ) c l k ( g ) i su n i q u e l yd e t e r m i n e df o re a c h 女 ( 2 ) gi sh a m i l t o n i a n c o n n e c t e di fa n do n l yi fc l a ( g ) i sh a m i l t o n i a n c o n n e c t e d a n d ( 3 ) gi sh o m o g e n o u s l yt r a c e a b l ei fa n do n l yi fc 1 2 g ) i sh o m o g e n o u s l yt r a c e a b l e h e n c eh a m i l t o n i a n - c o n n e c t e da n d ，l o 竹1 0 9 e n o u s f 可t r a c e a b l ea 1 os t a b l ei nc l a ( g ) a n dc 1 2 ( g ) e s p e c t i v e l yi nt i l et h i r dc h a p t e r ，w em a i ns t u d ys t a b l ep r o p m t i e so f ( k l ，4 ；2 ) 一 g r a p hs i n c e ( 1 4 ：2 ) 一g i a p hc o n t a i n sc l a w f r e eg r a p h t i l eu n s t a b l ep r o p e r t i e so fc l a w 一 ，? e eg r a p ha r ea l s ol i l t s | a b l et o ( k i ，4 ；2 ) 一g r a p hs ow eo n l yw o r ko u ts t ，a b l ep r o p e r t i e so f ( 1 、4 ；2 ) 一g r a p h i n t h i sc h a p t e r ，t h m e a r e f o u rs e c t i o n s i n t h e f i r s t , s e c t i o n ，w e p l e v e t h e o r e n l 31 0a n dt h e o r e m3 1 1 t h e o r e m31 0l e tgb ea ( k 1 ，4 ；2 ) 一g r a p h i fgi san f r e eo rk lv 只一f r e e g r a p h ，e l ( c ) i ss t i l la ( k i ，4 ；2 ) 一g r a p h t h e o r e m3 1ll e tgb ea ( k 1 ，4 ；2 ) 一g r a p h i fgi sa 码f r e eo rk 1v 只一f r e e g r a p h ，c l ( g ) i sw e l l d e f i n d e d i nt h es e c o n ds e c t i o n ，w ep r o v et h e o r e m3 1 2a n dg i v ei n f i n i t e l ym a n y ( k 1 4 ；2 ) g r a p h sgs u c ht h a tc l ( o ) i sh a m i l t o n i a nw h i l egi sn o th a m i l t o n i a n ，w h i c hi l l u s t r a t e s 些壅盟堇丕兰堕主兰垡堡塞 t h a tt h ec o n d i t i o n t a f r e eo rk 1vp 4 - f r e e i nt h e o r e m3 1lc a nn o tb ed e l e t e d w e a l s og i v ei n f i n i t e l ym a n yg r a p h sw h i c hs a t i s f yt h ec o n d i t i o ni nt h e o r e m3 1 2w h i l ed on o t i nt h e o r e m3 1 t h e o r e m31 2l e tgb ea ( k i ，4 ；2 ) 一g r a p hi fgi sat a f r e eo rk lv p 4 一f r e e g r a p h ，c ( a ) = c ( d ( g ) ) c o r o l l a r y3 1 3 l e tgb ea ( k 1 4 ；2 ) 一g r a p h i fgi sa 乃一f r e eo rk lvp 4 一f r e e g r a p h ，gi sh a m i l t o n i a ni fa n do n l yi fc l ( g ) i sh a m i l t o n i a n i nt h et h i r ds e c t i o n ，w ep r o v et h e o r e m3 1 4a n dg i v ei n f i n i t e l ym a n y ( k t 4 ；2 ) 一g r a p h s gs u c ht h a tc l ( g ) i st r a c e a b l ew h i l egi sn o tt r a c e a b l e ，w h i c hi l l u s t r a t e st h a t , t h ec o n - d i t i o n t a i r e eo rk ivp 4 一i r e e i nt h e o r e m31 4c a nn o tb ed e l e t e d w ea l s og i v e i n f i n i t e l ym a n yg r a p h sw h i c hs a t i s f yt h ec o n d i t i o ni nt h e o r e m3 1 4w h i l ed on o ti nt h e o r e i n 3 3 t h e o r e m3 ，1 4 l e tgb ea ( 1 4 ；2 ) 一g r a p hi fgj sa 乃一f r e eo rk 1v 只t e e g r a p h ，p ( a ) = p ( e l ( a ) ) c o r o l l a r y31 5 l e tgb ea ( k t 4 ；2 ) 一g r a p h i fgi saz _ ，r e po rk lv b 一，r e p g ia p h ，gi st r a c e a b l el fa n do n l yi fc l ( a ) i st r a c e a b l e i nt h ef o u r t hs e c t i o nw ep r o v et h e o r e m31 6 w ea l s og i v ei n f i n i t e l ym a n yg r a p h s w h i c hs a t i s f yt h ec o n d i t i o ni nt h e o r e m31 6w h i l ed on o ti nt h e o r e m3 9 t h e o r e m3 1 6l e tgb ea ( k i ，4 ；2 ) 一g r a p hi f gi sa 乃，k lvp 5 ) 一，7 e eo ik 1vp 4 一 f 7 e eg r a p h ，gi sh a m i l t o n i a n c o n n e c t e di fa n do n l yi fc l k g ) i sh a m i l t o n i a 7 l c o n n e c t e d i nt h ef o m t hc h a p t e r ，w es t u d yt h eh a m i l t o n i e i t yo fc o n n e c t e d ，n 2 一l o c a l l yc o n n e c t e d a n d ( k ll ；2 ) - g r a p h w ep r o v et h e o r e m 4 2w ea l s og i v eag 】a p hw h i c hs a t i s f i e st h e c o l j d i t i o ni nt h e o r e m4 2w h i l ed o e sn o ti nt h e o r e m4 1 t h e o r e m411 7 l e tgb eac o n n e c t e d ，n 2 一l o c a l l ye o n n e c t e dc l a w 一，e eg r a p hw i t h o u tv e r t i c e so f ( t e g l e el , w h i c hd o e sn o tc o n t a i na ni n d u c e ds u b g r a p hhi s o m o r p h i cg 1 0 1 g 2s u c ht h a tn ( v ) o fe v e r yv e r t e x o fd e g r e e4i n 片i sd i s c o n n e c t e dt h e , , gi s h a m i l t o t t i a l t t h e o r e m4 2 i ti ss h o w nt h a tl e tgb eac o n n e c t e d ，n 2 l o c a l l yc o n n e c t e d ( k 1 4 ；2 ) 一 g r a p hw i t h6 6 , w h i c i ld o e sn o tc o n t a i na ni n d u c e ds u b g r a p hhi s o m o r p h i ct o o n eo f g 1 ，g 2a n dg3 t h e ng i sh a m i l t o n i a n k e y w o r d s ：( k l ，口；q ) - g r a p h ，l o c a l l yk - c o n n e c t e d ，2 一l o c a l l yc o n n e c t e d ，k c l o s u r e c l a s s f i e a t i o n ：0 1 5 7 坐丕堕整盍堂堡主芏焦鲨塞i 第一章引言 本文仅考虑有限、无向、简单图，所用的记号和术语约定如下，其中未加说明 的部分请参照文献【1 设g 是一个图，v ( g ) ，e ( g ) 分别表示g 的顶点集和边集，记作g ：( y ( g ) ，e ( g ) ) 对于sc 矿( g ) ，u 矿( g ) 及g 的子图日，令n h ( “) = “v ( h ：u 。曰( g 儿 1 日i 2 i v ( h ) l ，g 的由s 导出的子图记为g s 】；g v ( g ) 一司也记为g sn g ( u ) 也简 记为( ”) ( 称为”的第一型邻域) 若”v ( g ) 满足g 【g ( ”) 是一连通的，则称。 为局部一连通点局部1 一连通点也称为局部连通点对于。矿( g ) 及g 中一条 边x y e ( g ) ，若z u 9 ，。口e ( g ) 或y v e ( g ) ，则称边。与点口邻接与u 邻接的所有边的导出子图称为”的第二型邻域，记为2 ( ”，g ) ：2 ( 。) 若对g 中 任意一点”，g 【n ( ”) 】连通，刚称g 局部连通同样地，若对g 中任意一点。，2 ( 。) 连通，则称g 是2 一局部连通的 f 为一个图，图g 称为f 一，。的，若g 中 没有同构于f 的导出子图当f 同构于i 、3 时，f ，r e e 图即无爪图 设p 是g 的一条( z ，) 一路( 以z ，为端点的路) ，如果g 中不存在( x ，) 一路p 使得1p l lpi ，则称p 是一条最短的( 。，) 一路g 的周长是指g 中最长圈的长， 记为c ( g ) ，g 中最长路的长记为p ( g ) 用尸k 表示含有，n 个点的路令l v ( g ) l = ，。 若c ( c 1 = 7 。，则称g 为h a m i l t o n 图；若对任意的1 , 3 c 曼g 中有长为f 的圈，则 称g 为泛圈的若对任意的l , g 中有过每个点的长为i ( 3 曼l n ) 的圈，则称g 为点 泛圈的；若对g 中任意圈e ，如果；y ( e ) i ，z ，则g 中存在蠲c 满足v c ) cv ( c ，) 且l v ( c l = 1 y ( e ) 1 + l ，则称g 为圈可扩的类似地，若v ( c ) = r t l ，则称g 为可迹 的，即g 中含有h a m i l t o n 路；若对g 中任意一点u ，g 中有以 为端点的h a m i l t o n 路，则称g 为齐次可迹的；若对g 中任意不同点”，g 中有( u ，”) 路为h a m i l t o n 路，则称g 为h a m i l t o n 连通的；若对g 中任意路p ，如果1 p l n ，则g 中存在 ( u ，u 1 路p ，满足v ( p ) cv ( p ) 且l v ( p ) 卜l v ( p ) i + 1 ，则称g 为路可扩的 一个局部连通点”称为适宜的，若g f a 0 ( u ) 不是完全图 坛l ( g ) 表示g 中所有适宜点的集合对g 中一个适宜点“，连接g n g ( v ) 】中的不相邻顶点得图 g 。，使得g 7 【 k ( u ) 1 为完全图，称作图g 在点。的局部完备对匮g ，令g o = g ，g l ，g 2 ，g ，= h ，g ：+ l 由g 。在g 。的一个局部k 一连通的适宜点2 ：i 局部完备所 得，1 i r 1 若日中没有局部。连通的适宜点，则称日为图g 的- 闭包， 记为c f ( g ) 当= l 时，c l ( g ) = c l ( g ) 又称为g 的闭包 设p 3 ，口1 是整数，g 中同构于k l ，p 的子图叫g 的一个p 一爪用 ( 2 3 0z z 。) 表示以 z o ，z 1 ，却) 为顶点的p 一爪，并约定记号中的第一个顶点z o 些塞蛭塾盔堂堡主堂堡鲨整一卫 表示该p 一爪中的p 度顶点，如果对g 的任一个p 爪( z d ，z ，嘞) ，均有f 曰( g 【 z 1 ，z 2 唧) 】) l q 则称g 为【k 1 ；q ) 一图( k 】，3 ；1 ) - 图即无爪图令k 1 ，3 = z o 、z l ，9 2 ，z 3 ) ，配 = x 2 y ，k 1 3u k 2 所得的图我们记作乃 1 9 9 7 年，z d e n kr y j g e k 在1 4 中提出了一种新的闭包概念令一是个图 类，若对于。中任意的图g ，c t k ( g ) 1 ，则称1 ，是k 闭包下的稳定图类令秽是女 闭包下的稳定图类，对于口中任一图g ，若g 有性质当且仅当c k ( g ) 有性质， 则称性质为一闭包下的稳定性质对于无爪图g ，c l 女( g ) 是唯一确定的并且图的 许多h a m i l t o n 性质是稳定的，对m 连通无爪图，r y j d a e k 等人证明了以下的结 论： 定理3 1 i4 】若g 为无爪图，则( 1 ) c z ( c ) 是唯一确定的；( 2 ) c ( a ) = c ( c l ( g ) ) 推论3 2 若g 为无爪图，则g 为h a m i l t o n 图当且仅当c l ( g ) 为h a m i l t o r t 图 定理3 删若g 为无爪图，则v ( c ) = p ( c f ( g ) ) 推论34 【5 】若g 为无爪图，则g 可迹当且仅当c l ( g ) 可迹 定理3 5 f 5 l 对任意整数n 1 4 ，存在n 阶的2 一连通无爪图g 使得c l ( g ) 为齐 次可迹的，但g 不是齐次可迹的 定理36 对任意整数，n 2 ，存在m 一连通无爪图g 使得c l ( g ) 为泛圈的，但 g 不是泛圈的 定理3 7 【5 1 对任意整数m 2 ，存在m 一连通无爪图g 使得c l ( g ) 为点泛圈的， 但g 不是点泛圈的 定理38 ( 5 l 对任意整数m 2 ，存在m 连通无爪图g 使得c t ( g ) 为圈可扩的， 但g 不是圈可扩的 因此我们可知周长，最长路长是闭包下的稳定性质对t n 一连通无爪图，当m2 2 时，泛圈，点泛圈，圈可扩都不是闭包下的稳定性质对无爪图，存在无穷多的图 g 满足c l ( g ) 为h a m i l t o n 连通的，但是g 不是h a m i l t o n 连通的可见h a r n i l l o f t 连通与齐次可迹也不是闭包下的稳定性质为了解决这一问题，1 9 9 9 年，b o l l o b d s 等人在f 6 i 中对闭包这一概念做了推广，提出了k 一闭包的概念并证明： 定理39 6 g 为无爪图，则 ( 1 ) 对任意的k ，c l k ( g ) 是唯一确定的； ( 2 ) g 是h a m i l t o n 连通的当且仅当c 1 3 ( g ) 是h a m i l t o n 连通的； ( 3 ) g 是齐次可迹的当且仅当c 1 2 ( a ) 是齐次可迹的 因此h n m i l t o n 连通和齐次可迹分别为c 1 3 ( g ) 和c 1 2 ( g ) 下的稳定性质 本文中我们主要利用闭包这一有力工具研究( k 1 ，4 ；2 ) 一图的一些h a m i l t o n 问 坐奎垣蔓盔堂堡主兰鱼堡壅鱼 题的稳定性 关于无爪图的h a m i l t o n 性已经有很多的结果，其中很多结果中用到了局部连 通的条件在【14 中，定义了第二型邻域的概念，并定义了2 局部连通由定义 易见每一个局部连通图必为2 一局部连通图许多用第一型邻域研究的关于无爪 图的h a m i l t o n 问题可以用第二型邻域的条件来研究所以关于无爪图的h n m i l t 。n 问题中有许多的结果可以把局部连通的条件降低到n 2 一局部连通，也已经取得了很 多好的结果，见【1 5 - i t s 在【7 中对无爪图r y j d s e k 用第二型邻域的条件给出了无 爪图为h a m i l t o n 图的一个充分条件 定理4 删若g 为连通，2 局部连通，6 2 的无爪图。如果g 中不含有 同构于g i 或c 2 ( 见图4 1 42 ) 的导出子图，满足h 中的4 度顶点在g 中不是局 部连通的，则g 为h a m i l t o n 图 本文中我们用第二型邻域的条件给出了( k ；2 ) 图为h a m i l t o n 图的一个充分 条件 出丕竖整盔兰堡兰垡堡塞 第二章( k 。，；q ) - 图 对无爪图类的h a m i