（应用数学专业论文）y3v3free图的哈密尔顿问题.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位删乍者繇每当、芬 导师签字 学位论文版权使用授权书 瓣 本学位论文作者完全了解堂控有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂 查l 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：乓私钆 签字日期：2 0 0 b 年f 胡呼目 导师签字： 立瓣 签字日期：z o o g 年。月甲日 山东师范大学硕士学位论文 y 3 一f r e e 图的哈密尔顿问题 中文摘要 哈密尔顿问题一直是图论中近几年来研究的一个热点，这从国际上几种著名 的数学刊物及国内几种核心数学期刊发表的文章可见一斑。判断一个图在什么条 件下是一个哈密尔顿图即所谓的哈密尔顿问题。而禁用子图的哈密尔顿问题是哈 密尔顿问题研究重要的研究领域之一。无爪图( c l a w f r e eg r a p h s ) 是禁用子图研究 最为深入的一个图类。关于无爪图的哈密尔顿问题，目前已有很多出色的且较为 成熟的结果。同时与无爪图相关的且比无爪图更广的图类一如几乎无爪图( a l m o s t c l a w f r e eg r a p h s ) 、半无爪图( q u a s i c l a w f r e eg r a p h s ) 的研究更是方兴未艾，新的结 果层出不穷。 本文采用“强思维”与“弱思维”的方式首次研究了一种比无爪图更广的图 类k 以一f r e e 图的哈密尔顿问题，这些结果拓展了哈密尔顿问题的研究。 首先本文在第二章第一节研究了在连通、局部连通条件下t k f r e e 图的哈密 尔顿性。在连通局部连通条件下存在e e f r e e 图是非哈密尔顿图；甚至存在连通 度、局部连通度任意大的k 以，f r e e 非哈密尔顿图。图的最长圈的研究常常会促进 图的哈密顿性的研究。进一步研究e 吒一f r e e 图的最长圈得至本文的第一个重要结 果( 第二章第一节) ： 定理1 1 1 若g 是顶点数不小于3 的连通、局部连通五一f r e e 图，则g 的最长 圈为控制圈，且g 是局部泛圈图( s u b p a n c y c l i cg r a p h s ) 。 本文在第二章第二节接着探讨在连通局部连通条件下k k f r e e 图成为哈密 尔顿图的条件。得到了下面的结果( 第二章第一节) ： 定理2 1 2 顶点数不小于3 的连通、局部连通一f r e e 、爪心独立图是完全圈可 扩的。 并得到了下面的两个推论： 推论2 1 1 顶点数不小于3 的连通、局部连通k f r e e 、几乎无爪图是完全圈可扩 山东师范大学硕士学位论文 的。 推论2 1 3 顶点数不小于3 的连通、局部连通z l - f r e e 、几乎无爪图图是完全圈可 扩的。 这些定理与推论是本文的第二个重要结果，它给出了几乎无爪图是完全圈可 扩图的两个充分条件，比较经典的充分条件是z d e n i kr y j a e e k 给出的，见下面 的定理： 定理若g 是顶点数不小于3 的连通、局部连通k 。一f r e e 、几乎无爪图则g 是完 全圈可扩图。 闭包方法是解决啥密尔顿问题的重要手段和方法。本文最重要的创造性工 作在于一种无爪图闭包的构造及一种艺一f r e e 图类的闭包构造与稳定性讨论。在 9 7 年z d e n e kr y j a i e k 定义了无爪图中的一种闭包概念，解决了无爪图中的一系 列哈密尔顿问题。设计一种无爪图中比z d e n i kr y j a i e k 闭包更多边的闭包是哈 密尔顿问题闭包研究一个努力的方向。z d e n i kr y j a e e k 闭包的构造着眼于局部 连通点增加边。本文在此基础上同时着眼于一定条件下的局部不连通点，构造了 一种无爪图中比z d e n i kr y j a e e k 定义的闭包更强( 增加更多边 的闭包，并证 明了保持周长不变且是唯一的。本文的第三章第二节从缩小加边范围出发构造了 一种比无爪图更广图类l 匕一矗图的闭包并进行了一些稳定性讨论。 本文第四章研究了半无爪图泛圈的一种充分条件。半无爪图作为比无爪图 更广的图类是由a i n o u c h e 在9 8 年首次提出，e t 前已有较多的研究结果。本文的 结果可作为半无爪图泛圈研究的一个丰富与补充。 关键词无爪图；几乎无爪图；半无爪图；泛圈；完全圈可扩；闭包；哈密尔顿 问题 中图分类号0 1 5 7 4 山东师范大学硕士学位论文 t h eh a m i l t o n i a np r o b l e m so fe k f r e eg r a p h s a b s t r a c t h a m i t o n i a np r o b l e m si so n eo ft h e h o ta r e a so ft h er e s e a r c h e so fg r a p h t h e o r y a n dt h i st e n d e n c yc a l lb es e e nf r o mt h el a r g ea m o u n to fa r t i c l e so nt h i sf i e l d o nt h ek e yi n t e r n a t i o n a lm a t h e m a t i c sm a g a z i n e sa n da sw e l la st h ed o m e s t i ck e y m a t h e m a t i c sm a g a z i n e s d e t e r m i n i n gc o n d i t i o n su n d e rw h i c hag r a p hc o n t a i n sa s p a n n i n gc y c l ei ss oc a l l e dh a m i t o n i a np r o b l e m s t h ef o r b i d d e ns u b g r a p h sp r o b l e m i so n eo ft h em o s ti m p o r t a n tr e s e a r c hf i e l d so nh a m i l t o n a i np r o b l e m s t h ec l a w - f r e e g r a p h si st h em o s tw e l lr e s e a r c h e dg r a p h sr e l a t e dw i t hf o r b i d d e ns u b g r a p h s n o w a d a y s t h e r ea r ed o z e n so f g o o d r e s u l t so nc l a w f l e e g r a p h s a n d f u r t h e l n l o r e t h el a r g e rc l a s so fg r a p h sr e l a t e dw i t hc l a w f r e eg r a p h ss u c ha sa l m o s t c l a w f r e e 伊印h s ，q u a s ic l a w - f r e eg r a p h sa r o u s e dt h ee n t h u s i a s m so fm a n yp e o p l et o f o c u st h e i rr e s e a r c h e so nt h i sf i e l d a l t h o u g ht h en e wr e s u l t so nt h el a t t e rt w ok i n d so f g r a p h sa p e a r so n e a f t e ra n o t h e r , t h er e s e a r c hi sf a rf r o mt h ee n d i nt h i sp a p e r , w er e s e a r c h e dt h eh a m i t o n i a np r o b l e m so nt h e 匕一f r e eg r a p h sa t t h ef i r s t t i m e t h e 五匕一f r e eg r a p h si s ac l a s so fg r a p h sl a r g e rt h a nt h ec l a w f r e e g r a p h s t h er e s u l t so f t h i sp a p e re x t e n d e dt h eh a m i t o n i a np r o b l e m sr e s e a r c h f i r s t l yw er e s e a r c h e dt h eh a m i t o n i a np r o p e t i e so f t h e 墨- f r e eg r a p h su n d e rt h e c o n d i t i o n st h a tc o n n e c t e da n dl o c a lc o n n e c t e d t h e r ea r ee x a m p l e ss h o wac e r t a i n 匕f r e eg r a p h s m a y b e n o n h a m i l t o n i a no nt h ec o n d i t i o n sm e t i o n e d a b o v e ，f u r t h e r m o r e ，t h e r ee x i s t s 匕圪一f r e eg r a p h sw i t ha r b i t r a r i l yh i g hc o n n e c t i v i t y a n dl o c a lc o n n e c t i v i t yw h i c ha r en o n h a m i l t o n i a n t h er e s e a r c ho ft h el o n g e s tc y c l e s w i l lp r o m o t et h eh a m i t o n i a np r o b l e mr e s e a r c h f u r t h e rr e s e a r c ho nt h el o n g e s tc y c l e s o fl 一f r e eg r a p h sg o tt h ef i r s ti m p o r t a n tr e s u l t so f t h i sp a p e r ： t h e o r e m1 1 1i fi sgac o n n e c t e da n dl o c a lc o n n e c t e d 墨匕一f r e eg r a p ho fo r d e r s 山东师范大学硕士学位论文 l a r g e r t h a n 3 , t h e nt h el o n g e s tc y c l eo fgi sd o m i n a t i n gc y c l ea n dgi s s u b p a n c y c l i c t h es e c o n dp a r to fc h a p t e r2d i s c u s s e dt h ec o n d i t i o n su n d e rw h i c ht h e 匕以一f r e e g r a p h st ob eh a m i l t o n i a ng r a p h sa n dg o tt h en e x tt h e o r e m ： t h e o r e m2 1 2i fgi sac o n n e c t e dl o c a lc o n n e c t e d 匕- f r e eg 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 so na tl e a s t3v e r t i c e s ，t h e ngi sf u l l yc y c l ee x t e n d a b l e n e x ta l et w oc o r o l l a r i e so f t h i st h e o r e m c o r o l l a r y2 1 1i fgi sac o n n e c t e dl o c a lc o n n e c t e d 匕一f r e ea n da l m o s tc l a w - f r e e g r a p ho na tl e a s t3v e r t i c e s ，t h e ngi sf u l l yc y c l ee x t e n d a b l e c o r o l l a r y2 1 3i fgi sac o n n e c t e dl o c a lc o n n e c t e dz l f r e ea n da l m o s tc l a w f r e e g r a p ho na tl e a s t3v e r t i c e s ，t h e ngi sf u l l yc y c l ee x t e n d a b l e t h e o r e mba n dt h ec o r o l l a r i e sa l et h es e c o n di m p o r t a n tr e s u l to ft h i sp a p e r , w h i c h g i v e sas u f f i c i e n tc o n d i t i o nf o r t h ea l m o s tc l a w f r e eg r a p h st ob ef u l l yc y c l e e x t e n d a b l e a n dt h ew e l lk n o w ns u f f i c i e n tc o n d i t i o ni sg i v e nb yz d e n 石kr a j a 苞e k ，s e e n e x tt h e o r e m ： t h e o r e mi fgi sac o n n e c t e dl o c a lc o n n e c t e d k 1 4 一f r e ea n da l m o s tc l a w f r e e g r a p ho na tl e a s t3v e r t i c e s ，t h e ngi sf u l l yc y c l ee x t e n d a b l e t h em o s ti m p o r t a n ta n dc r e a t i v ew o r ko ft h i st h e s i si st h ec r e a t i o no fan e w c l o s u r ec o n c e p to nc l a w - f r e eg r a p h sa n dt h ed e f i m t i o no fc l o s u r ec o n c e p to n e 匕- f r e eg r a p h s z d e n 石kr a j a 6 e kd e f i n e dac l o s u r ec o n c e p ti n19 9 7a n ds o l v e da s e r i e so fh a m i t o n i a np r o b l e m s a n ds u e n g t h e nt h ec l o s u r ec o n c e p tc r e a t e db y z d e n 石kr a j a 石e ki so fg r e a ts i g n i f i c a n c et ot h er e s e a r c ho fh a m i t o n i a np r o b l e m s t h e z d e n 石kr a j a 苞e k sc l o s u r ec o n c e p ti sr e l a t e dw i t ht h el o c a lc o n n e c t e dv e r t i c e s b a s e d o nt h ew o r ko fz d e n 吝kr a j a 6 e k ，w ep a ya t t e n t i o nt ol o c a lu n c o n n e c t e dv e r t i c e s b e s i d e so ft h el o c a lc o n n e c t e dv e r t i c e st oc r e a t e dan e wc l o s u r ec o n c e p t ，w h i c hi sa s t r e n g t h e n i n g o ft h ec l o s u r e c o n c e p t c r e a t e db yz d e n 否kr a ja 琶e k ( a d dm o r e 6 虫至塑蔓查兰堡主堂堡堡苎一 e d g e s ) w cp r o v e dl a t e ri nt h i sp a p e r t h en e wc l o s u r ek e e pt h ec i r c e m e f e r e n c es t a b l e a n di su n i q u e i nt h es e c o n dp a r to fc h a r p t e r3 , w ed e f i n e dac l o s u r ec o n c e p t o n e 以f l e eg r a p h su n d e rt h et h o u g h to fs h r i n k i n g t h es c o p eo fe d g ea d d i n ga n d d i s c u s s e dt h es t a b i l i t y i nc h a r p t e r4 , w er e s e a r c h e dak i n do fs u f f i c i e n tc o n d i t i o n f o rq u a s i c l a w f r e e g r a p h st ob ep a n c y c l i c t h eq u a s i c l a w - f r e eg r a p h si sa c l a s so fg r a p h sl a r g e rt h a nt h e c l a w f r e eg r a p h s n o wt h e r ea r el o t so fr e s e a r c h e so nq u a s i c l a w i f r e eg r a p h sw h e n i t w a sf i r s t l ym e n t i o n e db ya i n o u c h ei n1 9 9 8 a n do u i r e s u l ti nt h i sp a p e ri m p r o v e dt h e r e s e a r c ho nq u a s i - c l a w f r e eg r a p h s k e yw o r d s ：c l a w f r e eg r a p h s ；a l m o s tc l a w - f r e eg r a p h s ；q u a s i 。c l a w f r e e g r a p h s ； p a n c y c l i c ；f u l l yc y c l ee x t e n d a b l e ；c l o s u r e ；h a m i l t o n i a np r o b l e m s 7 山东师范大学硕士学位论文 第一章符号概念简介及预备知识与研究背景 本章介绍一些符号概念及研究背景。 第一节符号概念简介及预备知识 本文考虑简单、无向、有限图。全文常见的记号和术语约定如下，部分术 语和记号因需要放在各章节介绍，未加说明的部分参考文献【i 】。设 g = ( 矿( g ) ，e ( g ) ) 表示一个图，其中y ( g ) ，e ( g ) 分别表示图g 的顶点集和边集。 对于s 矿( g ) ，g 的由s 导出子图记为( s ) 。a ( y ( g ) m ) 。简记为g m 。口( g ) 、 y ( g ) 分别表示g 的独立数、控制数。对g 的子母日、f ，( h ) = u ( “) ； ”e ，i h 有时记l v ( h ) h i ：n ( h ) n f 记为，( 日) 。图中的一个点“的在g 中邻域 表示为g ( “) = v v ( g ) i “v e ( g ) ) 。如果对任意“e v ( g ) ，l ，的邻域( “) 的 导出子图( ) ) 。是连通的，则称g 是局部连通图；相应地若( 乞 ”。是七一 连通的贝称g 是局部七一连通图本文中大多数地方把p ) 。，。o ) ，( ，6 ) k 分别简记为( s ) ，0 ) ，( ( 玎) ) 。 设g 和是两个不相交的图，则g 和目的联图g v 日是指把g 的每个顶 点和日的每个顶点之间连一条边得到的图。g 的子图日称为g 的控制图，若 e ( g 日1 = o 。 设p 是g 中一条( x ，力一路( 以x , y 为端点的路) 。如果g 不存在o ，力一路p ， 使 p i 聊 3 时是非哈密尔顿的( ( g k 。) = n m ) 。容易验证它是连通且局部连 通e 巧f l e e 图。不仅如此，存在连通度、局部连通度任意大的e 巧f r e e 非哈密 尔顿图，如图k 。v k 。当珂 m 3 r n ，m _ o o 时即是这样一个图。因此，研究 只k f r e e 图的最长圈是一个自然的考虑。g 的一个圈c 称为控制圈( 简记为d 圈) ，若e ( g c 1 = a 。哈密尔顿圈显然是一个控制圈。本文将证明下面定理： 定理i i i 若g 是顶点数不小于3 的连通、局部连通e 屹- f r e e 图，则g 的最 山东师范大学硬士学位论文 长圈为d 一圈，且g 是局部泛圈图。 定理中“局部泛圈”在第一章已经介绍，是指存在3 一圈到最长圈之间各种长 度的圈。 下面是该定理的几个推论： 推论1 1 1 设g 是顶点数不小于3 的连通、局部连通图e 职f r e e 图，若口占， 那么g 是哈密尔顿图。 证明：反证。由定理1 1 1 ，g 有一个d 圈。设c 是g 中最长的一个d 圈， 3 u v ( g c ，显然咙 ) u 是独立集。那么口d ( u ) + 1 ，矛盾。 一个图的平方图是指这样的图g 2 = ( 矿( wi “，v 矿( g ) ，d i s t ( u ，v ) 2 ”。 推论1 1 2若g 是顶点数不小于3 的连通、局部连通匕匕- f r e e 图，则g 2 是哈 密尔顿图。 推论1 i 3 中提到的图z l 是由丘中的一个点上悬挂一条边得到的图。 推论1 1 3 若g 是顶点数不小于3 的连通、局部连通e f r e e ，z i - f r e e 图，n g 的最长圈为d 圈，且g 是局部泛圈匿。 1 2 一些引理 下面是证明中需要用到的一些引理： 引理1 2 1g 是k f r e e 图，v v 矿( g ) ， 短的( 工，y ) 路，贝4 p i 5 。 证明：若i p f = 6 ，设p = x t x 2 x 3 x 4 x s x 6 的( 工，y ) 一路，贝4 ( v ，x 1 ，x 3 ) x ，z 6 ) 兰巧， 此矛盾完成了证明。 x , y ( v ) ，设尸是( ( v ”中一条最 ( = 墨氏= y ) 是( ( 功) 中一条最短 矛盾。类此，i p p 6 同样能得到巧， 以下引理1 2 2 和1 2 3 中总假定c 是g 中一个圈，g 中不存在长为i c i + l 的圈。引理1 2 2 的结论是显然的： 弓i 理1 2 2 设工矿( g ) v ( c ) ，j ，z n c ( 曲，则 1 y z 仨e ( c ) ，y z 一，y + z + 芒e ( g ) ； 2 当y y + e ( g ) 时，y z - , 弦+ ，x y - 2 ) x y ”e ( g ) ； 山东师范大学硕士学位论文 3 当y 一_ y + ，z z + e ( g ) 时，y z - 2 , y z “仨e ( g ) 。 引理1 2 3 设g 是连通、局部连通l 巧一f r e e 图，设日是g c 的一个连通分支， 且i h 除2 。若y n c ( h ) ，贝0 y - y + e e ( g ) 。 证明：反证，设y - y + 芒e ( g ) 。设x i x 2 e ( h ) 且n ( y ) ，考虑 ( 弘y - , ，+ ，x l ，x 2 ) 。g 是e f r e e 图，则x 2 y 一，x 2 y + 之一存在。设工2 y 一e ( g ) ( x 2 y + e ( g ) 时类似可证) 。g 是局部连通图，考虑( u ( x 1 ) ) 中最短( 工：，y ) 路p ， 设为( _ ) x 2 z i z 2 。，y ( 由引理1 2 1 ，1 r 3 ) 。情况1p n c = y ) 考虑 ( y ，y 一，y + ，z ，而) 。( y ，y - , y + ，z ，一) 兰巧或有长为 c l + l 的圈。情况2 p n c y )设p 上第一个在c 上的点为z ，则z ，y - , y ，y + 。若 z ；- z ，+ e ( g ) ，则y - x 2 而y c z i z ；c y 一是长为l c i + l 的圈。若z ；z j 芒e ( g ) 则 ( z ；，z j ，z ；，z h ，一) 兰z 3 ，矛盾。 1 3 定理证明 设c 是g 中的一个圈且c 不是控制圈，下面证g 中存在长为i c l + l 的圈。 若否，存在日是g c 的一个连通分支，且i h 2 。取c ，日中点y ，x 使 x y e ( g ) ，设p 是( ( 力) 中最短的( x , y 一) - 路且假定p 中除j c 外的其它点都在 c 上，否则调整工的选取。由引理1 2 1 ，i p i 5 。i p l 3 ，否则g 存在长为l c | + 1 的圈。下面分别就i p i _ 3 ，i p l = 4 ，i p 卜= 5 讨论如下： 1 i p l = 3 设p = x i x 2 工3 ( = x ，玛= y 一) 。由引理1 2 3 ，巧x 2 + e ( g ) 。 因x 2 y 一e ( g ) ，由引理1 2 2 ，g 有长为i c i + 1 圈，矛盾。 2 l p l = 4设p = x l 工2 x 3 x 4 ，( x 1 = x ，x 4 = y 一) 。由弓i 理1 2 3 ， 工；z ；，y y + e ( g ) 。此时我们考虑x ，巧，巧，y ，一) 。不妨设而x ；c y 一， 码y + o ；时由对称性类似可证。由引理1 2 2 、1 2 3x 3 工；，y - , 工；+ ，y 一。 屯- - 屯+ ，x ；y ，x ；x 。，y ，石； 仨e ( g ) ， 否则有长为lc i + 1 圈如下： 工】y q ；x j g ；x ；c y x 3 x 2 x l( 当x ；e ( g ) ) ；x i x 2 屯c y y + q ；艽；工；f l ( 当 x ；y e ( g ) ) ：x l x 2 x 3 c x ；x ；c x ；x ,( 当x ；x l e ( g ) ) ； 一 些查墅蔓查兰堡圭兰垡丝苎一 x ，婀( 一y + c x ；x ；c x ：一( 当y e ( ( ) ： t 墨- - l t + 而磊； ( 当 x ；x 。e ( g ) ) 。( x ，x ；，x ；，y ，上1 ) 兰e ，矛盾。 3 l p i = 5 不妨设_ x ；c y 一，_ y + ；时由对称性类似可证。由引 理1 2 2 ，1 2 3 x 3 工；，y 一，工；+ ，y 一一。 考虑, x i , x 3 , y - , y + ) 。显然有y 一， y + 甓e ( g ) ，| 司日寸x , x 3 ，而y 一仨e ( g ) i f f 则| p i 。4 由于g 是t 一f l e e 图，x 3 y + e e ( g ) 。我们考虑( 屯，z ；，y ，_ ) 。 巧x ；，x ；y ，x ；x 一，工；y ， 仨( g ) ，否则有长为ic i + 1 圈如下： x , x 2 x 3 y + c 丐e c x ；x ；c y x , ( 当e 以g ) ) ；x , x c y y + c k c x ；y x ， ( 当 x ；yee ( g ) ) ；工2 ( x ；工；c x ；j l ( 当z ；工l e ( g ) ) ；上i y x ；c y y + c x ；x ；c ，3 工2 x l ( 当y e ( g ) ) ：x i x 2 x 3 c x ；x ；c x ；x ,( 当五；z 。e ( g ) )。那么 ( 工，巧，巧，y ，而) 兰，矛盾。 综上，我们证明了若c 不是控制圈，g 中总存在长为j cj + 1 的圈。而由 g 是局部连通图，g 中每个点在3 - 圈上。综合上面的证明我们有下面的结论： g 的最长圈为d 一圈，且g 是局部泛圈图口 山东师范大学硕士学位论文 第二节k f r e e 完全圈可扩图 本节单独讨论巧f r e e 图完全圈可扩的条件，一f r e e 图是指不含巧作为导出 子图的图。 2 1 简介与主要结果 一个点称为爪心点，若此点为足。中度为3 的点。早在9 4 年， z d e n e kr y j a ”6 e k 在文献【1 0 】中首次提出了几乎无爪图的概念。第一章中已经介绍 无爪图、几乎无爪图，这里为了作一个比较，重新叙述如下。一个图g 称为无爪 图若g 中每一个点x ，口( c 砷) 兰2 。图g 称为几乎无爪图，若g 中存在一个独 立集a c v ( g ) ( 可能为空) ，口( ( x ) ) 2 当x 正4 ；而对于工a ，( | ( 瑚2 。 换句话说，g 是几乎无爪图若g 是局部2 控制的同时所有的爪心是独立的。既 然，( h ) s 口( h ) ，故无爪图是几乎无爪图，这说明几乎无爪图是比无爪图更广的 图类。 无爪图在连通、局部连通条件下，h e n d r y 证明了是完全圈可扩图。 而 z d e n e - - kr y j a e e k 举例指出在连通、局部连通条件下几乎无爪图不一定是哈密尔 顿图。 最后，在加强了条件一k 一f r e e 后，z d e n i kr y j a e e k 得到了下面的结论： 定理2 1 1 呻1 若g 是顶点数不小于3 的连通、局部连通足。一f r e e 、几乎无爪图则g 是完全圈可扩图。 从上一节开始讨论的巧一f r e e 图是与k 。一f r e e 图互不包含的图类。如图 k m v k n ( i q m 3 ) 是一f r e e 非k 1 4 一f r e e 图；另一方面本身是k 一f r e e 非 k f r e e 图。作为比无爪图更广的图类，上节已说睨了，连通、局部连通k f r e e 图不一定是哈密尔顿图。 这里的研究发现，在连通、局部连通条件下，v 3 f r e e 、几乎无爪图也是完全 圈可扩的。并且条件可进一步放低为：“连通、局部连通k f r e e 、爪心独立图” 仍然可证明是完全圈可扩的。 山东师范大学硕士学位论文 本节将证明下面定理： 定理2 1 2 顶点数不小于3 的连通、局部连通一f r e e 、爪心独立图是完全圈可 扩的。 在给出本节的几个推论之前，先说说与本节有关的、关于无爪图和其他禁用子图 的哈密尔顿问题研究的概况。对z , - f r e e 图，g o o d m a n 吲有下面结论： 定理2 1 3 设g 是2 一连通z ，一f r e e 无爪图，那么g 是哈密尔顿瞄。 后来b e d r o s s i a n i ”1 说明在此条件下g 是泛圈图若g 非圈。 由定理2 1 2 ，再从“一丘优图”与“z ，一f r e e 图”；“爪心独立图”与“几 乎无爪图”的关系立刻得至下面的几个推论： 推论2 1 1 顶点数不小于3 的连通、局部连通匕一f r e e 、几乎无爪图是完全圈可扩 的。 推论2 1 2 顶点数不小于3 附连通、局部连通z 1 - f r e e 、爪心独立图是完全圈可扩 的。 推论2 1 3 顶点数不小于3 的连通、局部连通z l - f r e e 、几乎无爪图是完全圈可扩 的。 上面的推论2 1 1 与推论2 1 3 给出了几乎无爪图完全圈可扩的两种充分条件。容 易验证上面的推论中，若条件改为“2 连通”皿l j 不一定是哈密尔顿图。 2 2 一些引理 下面是本节证明中需要用到的一些引理： 引理2 2 1g 是连通、局部连通图，v v v ( g ) 非爪心点，设p 是( ( v ) ) 中一 条最短的( 工，力路，则i p i 4 。 证明：若l p i 5 ，设p = x x 2 x 3 x 4 屯( = 五x 5 = y ) 是( ( v ) ) 中一条最短的 ( 工，) 路，则( v ，工，x 3 ，工s 是世”，矛盾。类此，l p | 5 同样能得到k ”，此矛 盾完成了证明。 以下引理2 2 2 假定c 是g 中一个瞬，g 中不存在扩圈。 山东师范大学硕i ? 学位论文 弓i 理2 2 2 设x v ( g ) y ( c ) ，y ，z n c ( 上) ，贝0 t x y 、，x y + 硭e ( g ) ： 2 当y - y + e ( g ) 时，f 一，y z + 仨e ( g ) 2 3 定理2 1 2 的证明 以下证明中设g 是满足定理2 1 2 条件的图。 由于g 是连通、局部连通图，g 中每个点都在一个3 圈上。下面我们证明g 中每一个圈c ，i c 斟v ( g ) | _ 1 ，存在圈c ，使v ( c ) c v ( c ) ，l c i = 4 c l 十l 。 设是g 中的爪心集，那么a 是独立集。首先我们有下面的论断：对于每一 个圈c c v ( g ) ，存在点w 矿( c ) a ，工聋y ( c ) h x w e ( g ) 。事实上，由于g 连 通。对c c 矿( g ) ，j 某个工芒v ( c ) ，v y ( c ) ，i v e ( g ) 。由于g 局部连通， 存在条( ( v ) ) 中最短的v 一) 路p ，设h 是p 上与x 相邻的c 上的第一个点。 彳是独立集，那么v 和不同时属于a 。我们把不属于a 的c 上那一点作为w 。 下面的证明中我们假定圈c 和x ，w 是这样选择的：在所有以矿( c ) 为点集 的圈中，使( w ) ) 中的( 墨w + ) 路q 最短，且假定c 不能通过x 扩展。w 不是爪心， 因此w w + e ( g ) 。设x = x o ， ，工2 ，以，工= w + 是路q _ h 的点。由于q 的最短 性，对于1 f k ，i f j | 2 时而工，芒e ( g ) 。由引理2 2 1 ，k 2 ；另外一方面 不考虑平凡情况，七2 l 。 首先讨论k = 2 。考虑( w ) x ，w 一，x 2 ) ，我们有w 一工：e ( g ) 否则 ( w , x ，w 一，工2 ) 兰k 。由对称性，不妨假设_ e x ；c w 一。 下面考虑( x 2 , x i ，x ；，w ) 。w + x i ，x ；x ；，x ；w ，w 薯e ( g ) 否则存在圈c l ： w x 2 c w + w + w ( 当w + = 工i ) ；帆2 w + c x ；x ；c w ( 当巧屯4 - e ( g ) ) ；w 2 c w w + c x ；w ( 当z ；w e ( g ) ) ；w x ；c w w + c x 2 w ( 当x ；w e ( g ) ) 。在圈c l 上z 2 和w 是相邻 的，q ，= ( x ，x 。，x ：) 是( ( w ) ) 中z ，c 一路，且i y ( q 1 ) h y ( q ) l ，这与q 的最短性相 矛盾。因此( 盖：，工；，z ；，w ) 兰k 耶。于是屯仨a ，那么葺硭a ，石i 工j e ( g ) 。而 z 2 4 - x , - ，工w 一否则存在扩圈w c x 2 w c 对畦j i 潮，、( 当x ；= x , - ) ；w c x ( x x i x w 山东师范大学硕士学位论文 ( 当z ? = w 一) 。下面我们考虑( x ：，x ；，j ；，_ ，w ) ，x i x ；，工；崔e ( g ) 否则存在扩圈 如下： w ，f x i x ；c w + 屯c x ? x ；c w ( 算i e ( g ) ) 和圈w x x l x ；c 百x j c w x 2 c w ( 一j j e ( g ) 。因此( 屯，z j ，x ；，w ) 釜巧，矛盾。 当k = i 时，x i w + ，否贝q 有扩圈x w w + w c x i 工。考虑“，z i ，j i ，w ，x ) 。 x 1 w 一e ( g ) ，耳i 工仨e ( g ) 否财由引理2 2 2 ，g 有扩圈；易知w x ? ，w x j 诺e ( g ) 。 ( x 。，j i ，x ，x ) 兰匕，矛盾。口 山东师范大学硕士学位论文 第三章一种无爪图及一种e - f r e e 图类的闭包与稳定性 本章的第一节定义了一种无爪图中比z r y j a ”6 e k 定义的闭包更强的闭包一 泛闭包，并证明了保持周长不变且是唯一的。本章的后一节定义了一种比无爪 图更广图类e 匕一矗e 图的闭包并进行了一些稳定性讨论。 第一节无爪图的泛闭包 z r y j a 6 e kf 2 】在9 7 年定义了无爪图中的一种闭包概念。这里先简要介绍 一下z r y j a e e k 无爪图闭包概念及与本节有关的结果。 g 中一个局部连通点x 称为适宜点( e l i g i b l e v e n e x ) ，若( _ 。( x ) ) 。不是团( 团指 g 中完全予图) 。若x 矿( g ) 是一个适宜点，则把| 。( 曲中不存在边的点之间加 边直到( k ( 力) 。成为一个团，称为对点x 的局部完备( 本章中涉及的局部完备 概念都是此思想，不再重述) 。z r y j a 它c k 定义的闭包就是不断把g 中的适宜点 作局部完备最后得到一个不含适宜点的图，称为g 的闭包。在文献f 2 】中 z r y j a 6 e k 介绍了无爪图闭包概念并得到了下面的结果： 定理1 1 1 设g 是无爪图，g 。是对适宜点工作局部完备得到的图，则 ( 1 ) g 。是无爪图 ( 2 ) c ( g x ) = c ( g ) 。 所有闭包方法通过增加边有助于判断一个图是不是哈密尔顿图。因此设计 一种无爪图中比z r y j a 6 e k 闭包更多边的闭包是一种努力的方向。从这个考虑 出发，h b r o s e r m a1 4 在2 0 0 1 年定义了一种无爪图中能增加更多边的闭包一圈 闭包，并证明了唯一性且保持周长稳定( s t a b l e ) 。这里“稳定”是指一个图g 的 闭包对g 的某一性质如无爪性、周长等保持不变。z r y j a 6 e k 闭包对不含适宜 点的图不能再增加边。而圈闭包的定义是从不含适宜点的图出发，对满足一定 条件的圈作圈完备，显然能增加更多边。本节定义的无爪图中泛闭包，也能对 山东师范大学硕士学位论文 某些不含适宜点的图增加一些边，它的考虑是从特定的局部不连通点出发的。 设x 是局部不连通点，k ，与足，：是组成( v 。( 曲) 。的两个团( 由无爪性) 。工 称为