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

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 ( 注：如没有其他需要特别卢 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 油屯熏 黝鲧旦嘞 学位论文版权使用授权书 本学位论文作者完全了解堂蕉有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权皇 奠可以将学位论文的全部或部分内容编入有关数据库进行检索，- ，r 以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：曲矿已蓬乙 、乡 引帷瓮2 蠕 签字日期：2 0 0 f , 年年月日 签字日期：2 0 0 年争月，o 日 山东师范大学硕士学位论文 若干图类的路和圈问题 曲晓英 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 路和圈是图的两种基本结构，是分析和刻画图的有力工具，有大量的实际问题可 以归结为图的路和圈问题，所以这方面一直是图论中的热点研究领域关于路和圈的 进展可参考【1 3 - 1 6 】事实上，图论中三大著名难题之一的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 问题往往比较困难，于是人们转而研究不 含有某些禁用子图的图类继b e i n e k e l 9 6 8 ，1 9 7 0 年发表的关于线图性质的两篇文章1 7 卜 【1 8 l 之后，人们开始关注包含着线图的无爪图7 0 年代末8 0 年代初，是研究无爪图的一个 非常活跃的时期关于无爪图方面的部分优秀成果可参考 2 h 4 】，【1 9 【3 3 】 3 4 是关于 无爪图的综述性的文章另外，无爪图的概念也被从不同角度推广到了更大的图类，如 半无爪图，几乎无爪图，( 1 ；2 ) 一图， 图等年， 在 7 】中定义了一, 4 d c t1 9 9 8a a i n o u c h e 种包含无爪图的更大的图类一半无爪图且给出了关于半无爪图的路和圈方面的一些 结果之后，很多专家学者相继做了大量工作来研究这类图的h a m i l t o n 问题且将无 爪图中的许多非常好的结果推广到了半无爪图其中，某些进展可参考 3 5 一 3 7 1 _ 1 9 9 4 年， z r y j s e k 3 8 定义了一种包含无爪图的更大的图类一几乎无爪图之后，亦出现了不 少研究这类图的h a m i l t o n 问题的学术论文如【3 9 - ( 4 1 1 但事实上，无爪图中许多很好 的结果要推广到几乎无爪图难度非常大所以，滕延燕，尤海燕2 0 0 3 年 5 在此基础上 提出了拟无爪图的概念，它包含无爪图类但却包含在几乎无爪图类中但是，在这个 概念下，很多至今还没有能够推广到几乎无爪图的无爪图中的非常好的结果却可以 推广到拟无爪图l 矿扩展图是我们在研究不同图类结构的基础上所提出的一种包 含k 1 卅1 一f r e e 图的新的图类v 独立集 z 。，z 2 ，) y ( g ) ( p 2 ) ，如果n ( x 1 ) n n ( x 2 ) n n ( x p ) ，那么若v u n ( 5 1 ) n ( 石2 ) n n ( x p ) ，有【“ n x 1 u n x 。】u u n i x ，】，则称u 为 z l ，士2 ， 的控制点否则，称珏为忙，z 2 ，唧) 的非控 制点将 z l ，z 2 ，) 的控制点组成的集合称为p ，x 2 ，昂 的控制集，记为d ( x l ，x 2 ， ，) ；扛l ，。2 ，) 的非控制点组成的集合称为 。，现，却 的非控制集，记为： 西( z l ，5 2 ，唧) v 独立集忙1 ，0 2 ，却) 矿( g ) 0 2 ) ，如果y ( x 1 ) n n ( x 2 ) n n ( x p ) 1 山东师范大学硕士学位论文 ，习巧4 d ( x l ，茹2 ，x p ) ，且若v u d ( x l ，。2 ，- - ，z p ) ，v v 面( z l ，z 2 ，一，z p ) ， 有“”e ( g ) ，则称g 为k i ，p - 扩展图特别地，耳i r 扩展图类是包含着无爪图类且比无 爪图类更大的图类本篇论文主要研究了无爪图，半无爪图，拟无爪图，。旷扩展图的 路和圈问题 在第章中，我们主要介绍了文章中所涉及的一些概念，术语符号和本文的研究 背景以及已有的一些结果 在第二章中，我们通过具体实例讨论了关于无爪图的已有的在不同连通条件下的 几个结果间的关系，证明了下面的结果： 定理2 5 无孤立点的三角连通的无爪图也是半局部连通的+ 推论2 6 ”边数不小于3 的三角连通的无爪图是点泛圈的”这个结果包含在”顶点数 不小于3 的半局部连通的无爪图是点泛圈的”这个结果中 在第三章中，我们探讨了半无爪图的最长路，点泛圈性以及闭包等问题，进一步改 进了m m a l t h e w s ，p ，s u m n e r ，r j f a u d r e e ，h o n g j i a nl a i ，c q z h a n g 等人的相应结果 定理3 1 ，3 连通半无爪图g 有h a m i l t o n 路或有长至少为2 谢g ) + 2 的路 定理3 1 4 设g 为连通半无爪图，若d ( g ) 兰( i gj 一2 ) 3 ，则g 有h a m i l t o n 路 定理3 4 2 边数不小于3 无孤立点的三角连通半无爪图是点泛圈的 定理3 5 4 顶点数不小于3 的半局部连通的半无爪图是点泛固的 定理3 5 5 设g 是连通度k ( g ) 2 的半无爪图，m ( g ) = 。v ( a ) ：( ( z ) ) 连 通) ，m ( g ) 是g 的控制集且( m ( g ) ) 有r 个连通分支，若r 忾( g ) ，则g 是h a m i l t o n 其 中咒( g ) 的下界r 是最好可能的且g 不一定是泛圈的 定理3 6 1 顶点数不小于3 的连通几乎局部连通半无爪图g 若满足6 ( g ) 3 ，则g 是 点泛圈的且其中d ( g ) 的下界是最好可能的 定理3 7 1 若g 是半无爪图，z 是g 的一适宜点，g 为由g 在。局部完备所得，n g 。仍是 半无爪图，但g 不一定是无爪图 推论3 7 2 若g 是半无爪图，n d ( a ) 是半无爪图 定理3 7 3 若g 是半无爪图，则d ( g ) 是唯一确定的 在第四章中，我们研究了拟无爪图的最长路，完全圈可扩性以及点可排序泛圈 性( v e r t e xp a n c y c l i co r d e r a b l e ) ，进一步推广了r j f a u d r e e ，r j g o u l d 等人的相应 结果 2 山东师范大学硕士学位论文 定理4 1 2 连通拟无爪图g 有h a m i l t o n 路或有长至少为2 d ( g ) + 2 的路 定理4 1 3 设g 为连通拟无爪图，若6 ( g ) “g i 一2 ) 3 ，则g 有h a m i l t o n 路 定理4 1 4 设g 为n 阶2 一连通拟无爪图，若n c ( n 一2 ) 2 ，则g 有h a m i l t o n 路 定理4 2 4 无孤立点的三角连通的拟无爪图是完全圈可扩的也是点可排序泛圈 的( v e r t e xp a n c y c l i eo r d e r a b l e ) 在第五章中我们定义了一种包含k z l p + 1 一f r e e 图的新的图类k - 1 p - 扩展图，探讨了它 的基本性质，证明了下面的结果： 定理5 2 1 无孤立点的三角连通的甄2 _ 扩展图是完全圈可扩的 关键词：半无爪图；拟无爪图；风, p - 扩展图；点泛圈的；h a m i l t o n 分类号：0 1 5 7 5 3 山东师范大学硕士学位论文 p a t h sa n dc y c l e si ns e v e r a lg r a p hf a m i l i e s q ux l a o y i n g 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 p a t h sa n dc y c l e sa r et w ob a s i cs t r u c t u r e so fg r a p h s i nf a c t ，m a n yp 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 dt ot h ep r o b l e mo fp a t h sa n dc y c l e s t h e r e f o r e ，t h er e s e a r c ha b o u t t h e mi sv e r ya c t i v e 。w h a ti sm o t e ，t h ef a m o u sh a m i l t o np r o b l e mi sa b o u tp a t h sa n d c y c l e so fg r a p hi ne s s e n c e d u r i n gt h er e c e n ty e a r s ，t h er e s e a r c hm a i n l yf o c u so nt h e f o l l o w i n ga s p e c t s ：h a m i l t o n i e i t y , p a n c y c l i s m ，v e r t e xp a n c y c l i s m ，t h el o n g e s tp a t h ( c y c l e ) e t c a n dw eh a v em a d eg r e a tp r o g r e s s h o w e v e r 】w ec a nn o td e n yt h ef a c tt h a ti ti s u s u a l l yv e r yd i f f i c u l tt os t u d yh 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 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 gs o m ef o r b i d d e ns u b g r a p h ss u c ha s c l a w - f r e eg r a p h s t h ef i r s tm o t i v a t i o nf o rs t u d y i n gp r o p e r t i e so fc l a w f r e eg r a p h sa p p a r - e n t l ya p p e a r e df 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 17 一 1 8 h o w e v e r ，t h e m a i ni m 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 r yc o m m u n i t yt ot h ec l a s so f c l a w f r e eg r a p h sw a sg i v e ni nl a t e7 0 sa n de a r l y8 0 s s o m ef a m o u sr e s u l t sa b o u tc l a w - f r e e g r a p h sc a nb es e e ni n 阱 4 ， 1 9 】- 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 w - f r e eg r a p hh a s b e e ne x t e n d e dt os e v e r a ll a r g e rg r a p hf a m i l i e si nd i f f e r e n tv i e w s ，s u c ha sq u a s i c l a w f r e e g r a p h s ，a l m o s tc l a w f r e eg r a p h s ，( k 1 ，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 ( 7 d e f i n e dan e wg r a p hf a m i l y _ t l u a s i - c l a w - f r e eg r a p h sa n dh ea l s og i v e ds e v e r a lr e s u l t sa b o u t p 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 t e rt h a t ，m a n yr e s e a r c h e r sh a v ed o n eal o t o fw o r kt os t u d yh a m i l t o np r o b l e mi nq u a s i c l a w f r e eg r a p h s 3 5 一 3 7 1 a l m o s tc l a w f r e e g r a p h sa r ed e f i n e db yz 冗y j e ki n 【3 s i ti sa l s oal a r g e rg r a p hf a m i l yt h a nt h a to f c l a w - f l e eg r a p h s h o w e v e r ，i ti sv e r yd i f f i c u l tt oe x t e n dm a n yg o o dr e s u l t so fc l a w f r e e g r a p h st oa l m o s tc l a w f r e eg r a p h s t h e r e f o r e ，t e n gy a n y a na n dy o uh a i y a ng a v et h e d e f i n i t i o no fs t r o n g l ya l m o s tc l a w f r e eg r a p h s 5 ，w h i c hc o n t a i nt h ef a m i l yo fc l a w - f r e e g r a p h sa n di sc o n t a i n e di nt h ef a m i l yo fa l m o s tc l a w - f r e eg r a p h s h o w e v e r ，m a n yg o o d r e s u l t so fc l a w - f r e eg r a p h st h a th a v en o tb e e ne x t e n d e dt oa l m o s tc l a w f r e eg r a p h sc a n b ee x t e n d e dt os t r o n g l ya l m o s tc l a w - f r e eg r a p h ss u c c e s s f u l l y t h ed e f i n i t i o no fk 1 ，p e x t e n d e dg r a p h sw a sp u tf o r w a r dw h e nw es t u d i e dt h es t r u c t u r eo fd i 髓r e n tg r a p hf a m i 山东师范大学硕士学位论文 l i e s l e t 2 ；1 ，x 2 ，昂) c v ( g ) ( v 2 ) b ea ni n d e p e n d e n tv e r t e xs e ts u c ht h a ti ts a t i s f i e s n ( x 1 ) nn ( x 2 ) n n ( z p ) 曲i ff o re v e r yu n ( x 1 ) nn ( x 2 ) n n ( 。p ) ，w e h a v e n x 1 un x 2 u k ，t h e nw es a yt h a t 让i sad o m i n a t i n gv e r t e xo f z l ，x 2 ，z p ) t h es e to f a l ld o m i n a t i n gv e r t i c e so f z l ，5 2 ，一，z p ) i ss a i dt ob ea d o m - i n a t i n gv e r t e xs e to f 茁1 ，z 2 ，- ，唧) ，w h i c hi sd e n o t e db yd ( 2 ；l ，2 7 2 ，。p ) s i m i l a r l y , t h e s e to fa l lu n d o m i n a t i n gv e r t i c e so f z l ，x 2 ，昂) i ss a i dt ob ea nu n d o m i n a t i n gv e r - t e xs e to f z l ，z 2 ，- ，。p ，w h i c hi sd e n o t e db y 百( 。l ，x 2 ，一，坼) l e t ( z 1 ，z 2 ，- - ，。p ) b e a n yi n d e p e n d e n tv e r t e xs e ti ny ( g ) ( p 2 ) i fn ( x 1 ) nn ( z 2 ) n 。nn ( z p ) 西，t h e n d ( z l ，。2 ，一，) 丸w h a t i s m o r e ，i f f o ra n yv e r t e xuo f d ( x l ，z 2 ，一，x p ) a n da n yv e r t e x o fd ( x i ，x 2 ，x p ) ，w eh a v e 札u e ( g ) ，t h e ngi sak 1 , p - e x t e n d e dg r a p h b yd e f i n i - t i o n ，w ec a ne a s i l yk n o wt h a tk 1 ，p + 1 一f r e eg r a p h sa r ec o n t a i n e di nk 1 , p - e x t e n d e dg 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 n dc y c l e so fc 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 ，s t r o n g l ya l m o s tc l a w - f r e eg r a p h sa n dk i p e x t e n d e dg 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 eb 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 l e 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 ea l s og i v es o m e r e l a t e dr e s e a r c hb a c k g r o u n d sa n ds o m ek 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 em a i n l ys t u d yt h er e l a t i o n sa m o n gs e v e r a lk n o w nr e s u l t so f c l a w - f r e eg r a p h sa n dg i v et h ef o l l o w i n gr e s u l t s ： t h e o r e m2 5 e v e r yt r i a n g u l a r l yc o n n e c t e d c l a w f r e eg r a p hw i t h o u ti s o l a t e dv e r t i c e s i sa l s oq u a s i l o c a l l yc o n n e c t e dc l a w - f r e e c o r o l l a r y2 6t h er e s u l to f ”e v e r yt r i a n g u l a r l yc o n n e c t e dc l a w - f l e eg r a p hg w i t h j e ( g ) l 3a n dw i t h o u ti s o l a t e d v e r t i c e si sv e r t e xp a n c y c l i c ”i sc o n t a i n e di n t h a to f ”e v e r yq u a s i l o c a l l yc o n n e c t e dc l a w f r e eg r a p hw i t hv ( c ) l 3i sv e r t e xp a n c y c l i c i nt h et h i r dc h a p t e r ，w em a i n l yo b t a i nt h er e s u l t sa sf o l l o w s t h e o r e m3 1 3i fgi sac o n n e c t e dq u a s i - c l a w - f r e eg r a p h t h e ngh a sap a t hw h i c h i se i t h e rh a m i l t o n i a no ro fl e n g t ha tl e a s t2 6 ( g ) + 2 t h e o r e m3 1 4i fgi sac o n n e c t e dq u a s i c l a w f r e eg r a p hw i t h6 ( g ) ( i g f 一2 ) 3 ， t h e ngh a sah a m i l t o n i a np a t h t h e o r e m3 4 2e v e r yt r i a n g u l a r l yc o n n e c t e dq u a s i c l a w f r e eg r a p hgw i t hi e ( g ) 3a n dw i t h o u ti s o l a t e dv e r t i c e si sv e r t e xp a n c y c l i c 山东师范大学硕士学位论文 t h e o r e m3 5 4 e v e r yq u a s i l o c a l l yc o n n e c t e dq u a s i c l a w f r e eg r a p ho fo r d e rn k3 i sv e r t e xp a n c y c l i c t h e o r e m3 5 5l e tgb eaq u a s i c l a w - f r e eg r a p ho fc o n n e c t i v i t y ，c ( g ) 22a n d m ( a ) = z v ( g ) ：( ( z ) ) i sc o n n e c t e d s u p p o s et h a tm ( g ) i sad o m i n a t i n gs e to f g a n d ( m ( g ) ) h a src o m p o n e n t s i fr 墨k ( g ) ，t h e ng i sh a m i l t o n i a n t h e o r e m3 6 1l e tgb eac o n n e c t e da l m o s tl o c a l l yc o n n e c t e dq u a s i c l a w - f l e e g r a p hw i t hv ( g ) 【3 i fd ( g ) 3 ，t h e ng i sv e r t e xp a n c y c l i ca n dt h el o w e rb o u n do f d ( g ) i sb e s tp o s s i b l e t h e o r e m3 7 1l e tgb eaq u a s i c l a w - f l e eg r a p ha n dl e t 。b ea de l i g i b l ev e r t e xo f g l e tg b eal o c a lc o m p l e t i o no fga t 。t h e nt h eg r a p hg i saq u a s i c l a w - f r e eg r a p h b u ti ti sn o ts u r et h a tg + i sac l a w - f r e eg r a p h c o r o l l a r y3 7 2l e tgb eaq u a s i c l a w f r e eg r a p h ，t h e nd ( g ) i ss t i i laq u a s i c l a w f r e eg r a p h t h e o r e m3 7 3l e tgb eaq u a s i c l a w f r e eg r a p h t h e nc t ( g ) i sw e l ld e f i n e d i nt h ef o u r t hc h a p t e r ，w em a i n l yi m p r o v es o m ec o r r e s p o n d i n gr e s u l t so fr j f a u d r e e ， r j g o u l de t c t h e o r e m4 1 2i fgi sac o n n e c t e ds t r o n g l ya l m o s tc l a w f r e eg r a p h 。t h e ngh a sa p a t hw h i c hi se i t h e rh a m i l t o n i a no ro fl e n g t ha tl e a s t2 6 ( g ) + 2 t h e o r e m4 1 3i fgi sac o n n e c t e ds t r o n g l ya l m o s tc l a w - f l e eg r a p hw i t hd ( g ) ( g i 2 ) 3 ，t h e ng h a sah a m i l t o n i a np a t h t h e o r e m4 1 4l e tgb ea2 - c o n n e c t e ds t r o n g l ya l m o s tc l a w - f r e eg r a p h i fn c ( i g 卜1 ) 2 ，t h e ng h a sah a m i l t o n i a np a t h t h e o r e m4 。2 4e v e r yt r i a n g u l a r l yc o n n e c t e ds t r o n g l ya l m o s tc l a w - f l e eg r a p hw i t h o u ti s o l a t e dv e r t i c e si sb o t hf u l l yc y c l ee x t e n d a b l ea n dv e r t e xp a n c y c l i co r d e r a b l e i nt h el a s tc h a p t e r ，w ed e f i n ean e wg r a p hf a m i l y - k r , p - e x t e n d e dg r a p ha n dg i v et h e n l l o w i n gr e s u l t t h e o r e m5 2 1e v e r yt r i a n g u l a r l yc o n n e c t e dk 1 ，2 一e x t e n d e dg r a p hw i t h o u ti s o l a t e d v e r t i c e si sf u l l yc y c l ee x t e n d a b l e k e y w o r d s ：q u a s i c l a w - f l e eg r a p h ；s t r o n g l ya h n o s tc l a w - f l e eg r a p h ；k i ，p e x t e n d e d 山东师范大学硕士学位论文 g r a p h ；v e r t e xp a n c y c l i c ；h a m i l t o n c l a s s i f i c a t i o n ：0 1 5 7 5 7 山东师范大学硕士学位论文 第一章预备知识 51 1 符号概念介绍 本文仅考虑有限无向简单图，所使用的记号和术语约定如下，其中未加说明的部 分请参照文献( 1 设g 是一个图，y ( g ) ，e ( g ) 分别表示g 的顶点集和边集对于 v ( a ) ，s ，tc y ( g ) 及g 的予图日，令n ( s ) = 口v ( g ) s ：q u s ，使得“u e ( g ) ) ，e ( s ，t ) = 时 e ( c ) ：s s ，t t ) i h i = i v ( h ) i 称为日的阶日的由5 导出的子图记为( s ) 日但) g 简 写为( s ) 若s y ( g ) y ( 日) ，令h ( s ) = n ( s ) ny ( 日) 若s = 口 ，则将( s ) 简 写蔓j n h ( v ) 令i v = n h ( u ) u 进一步，若h = e 则将( s ) ，蜥( u ) ，蜥阻】分 别简写为( s ) ，( ) 和m 若( ( u ) n ( ) ) v ( h ) 曲，则称g 的子图日满足性 质母h ( u ，”) u ，u y ( h ) ) 对g 的予图g 1 ，g 2 ，记g 1 a g 2 为由( e ( g ) ue ( g z ) ) ( g 1 ) n e ( g 2 ) ) 导出的g 的子图对g 中任意两点。，y ，( z ，g ) 一路定义为以。，可为端点的路日中最 短( 。，可) 路的长用d 日( 。，可) 表示d g ( z ，s ，) 常简写为d ( 。，g ) g 中经过g 的每个顶点恰一次 的路n g 的h a m i l t o n 路设p = v l u 2 唧为g 中一条路，符号地p 和p ( 1 i j p ) 分别表示p 的子路v i y i + 1 码和町一l v i v ( v i p v j ) = 让，3 i + 1 ，码 ，v ( v j p v i ) = f l ，v i ) 。f2 ，时。分别表示p 上的点v i f 和。l + ( 1si f i + fs p ) ，口f 1 ，讲1 也分 别记成 f 和谚对口y ( g ) ，若( ( ) ) 是连通的，则称 是g 的一局部连通的点g 中一 个局部连通的点z 称为适宜的，若( 口) ) 不是完全图对g 中一个适宜点z ，连接( ( ) ) 中 的不相邻顶点得n g ，使得( ( 口) ) g i 是完全图，此过程称作图g 在点z 的局部完备对 图g ，令g = g o ，g 1 ，g 2 ，g ，= h ，g 小o a g t 在g i 的一适宜点x i 局部完备所得( 1 茎i r 一1 ) ，若日中没有适宜点，则称日为图g 的闭包，记为d ( c ) 长为f 的圈叫f 一圈，过点集s 的f 圈叫( s ，f ) 一圈，( 口) ，1 ) 一圈简记为( 口，1 ) - 圈( 其中沩不小 于3 的整数) 若对g 中任意一点w 及任意满足3 f f g i 的整数f ，g 中有( 口，f ) 一圈，则 称g 足点泛圈的如果图g 满足：( 1 ) g 的每个顶点都在一个3 - 圈上；( 2 ) 对g 中任意一个 n c ，只要i v ( c ) 1 v ( c ) ，就存在g 的n c 。，使得v ( c ) v ( d ) j & l v ( c ) l = i v ( c ) + 1 ，则称g 是完全圈可扩的( 为了叙述方便，本文中将具有g 这种性质的圈口q 做n c 的扩 圈) 设i v ( c ) j = n ，对v v y ( g ) ，若存在以 开头的y ( g ) 的一个排序口l ，v 2 ，口。( u l = 口) 使得( 1 ， ) 是h a m i l t o n 的( 3 k n ) ，则称g 是点可排序泛圈的v e r t e x p a n c y c l i c o r d e r a b l e ) 设c = 口l 2 珥 1 是图g 的一r 一圈，陇，v j y ( g ) ( 1 i 1 ) 图3 1 2 ( 一) 定理3 1 3 的证明 设g 是满足定理3 1 3 条件的图即g 是连通的半无爪图 引理3 1 1 设g 是连通的半无爪图，且g 有长为r 的路p 但没有长为r + 1 的路，口 y ( p ) ，若( 口) 不全包含在y ( p ) 中，则u 一+ e ( g ) 证明设p = ”1 u 2 - v r + l ：因为g 中没有长为r + 1 的路，所p a n ( v i ) u ( 坼十1 ) y ( 尸) ， 从而 车 m ，v r ) ，由于( ) 不全包含在v ( p ) e e ，故存在z v ( c ) y ( 尸) ，使得z v e ( g ) 显然z 。一，。”+ 隹e ( g ) ，所口a d ( z ，”一) = 2 = d ( z ，口+ ) 由半无爪图的定义，存在y j ( 窖，v - ) ，且m n x 】u 一一 ，存在z j ( x ，口+ ) ，且旧n x u _ + i 论断( a ) 若y y ( 尸) ，n y = 口且口一矿e ( g ) ； ( b ) 若z y ( p ) ，n z = 口且口一。+ e ( g ) ； 证明( a ) 否则，若y y ( p ) ，但y v , n y y ( u 2 p 一2 ) u y ( ”+ 2 p 诈) 若y ( v 2 p v _ 2 ) ， 由一n ( y ) n ( x ) u ( 。一) 知y z e ( g ) 或y 一 一e ( g ) ，于是易得g 的长为r + l 的 路： 1 p y x y p v r + l 一z 层( g ) 时) ， i p y 一口一p y x v p v ，+ l ( 可一口一e ( g ) 时) ，矛盾若y y ( 口”p v ，) ，由一( g ) ( 工) u 0 一) 知g 一。e ( g ) 或y 一 一e ( g ) ，于是易得g 的 1 6 山东师范大学硕：仁学位论文 长为r + 1 的路：v l p y x y p v ，+ l ( f z e ( g ) 时) ， l 尸 一y l 毛z p 珥十l b 一口一e ( g ) 时) ，矛 盾由以上矛盾知，若y y ( 尸) ，则只能y = v 由矿n ( y ) ( z ) u 0 一) ，且”+ 。隹 e ( g ) 知u 一”+ f ( g ) ( b ) 类似于( a ) 的讨论易证 下面完成引理3 1 1 的证明 由上面的论断知玑。隹y ( p ) 若y = z ，则 一n ( z ) n ( x ) un ( v + ) ，又删一隹 e ( g ) ，从而w 一口+ e ( g ) 若y 。因为d ( v ， q ) = 2 ，所以存在 j ( y ，v - 2 ) 由论 断( a ) 知，y ( p ) ( 否则，w = v - - 且? 3 v 。e ( g ) ，则 1 p v - 2 v ：r z v + p 珥十l 为长为r + 1 的路) 若 = z ，贝l l y z e ( g ) ，从而 1 尸 一y z v + p v r + l 是g 中长为r + l 的路，矛盾若脚= x ，因 为w ) ，所以v y e ( g ) 或 口- 2 e ( g ) ，显然v y 隹e ( g ) ，若伽啊2 e ( g ) ，得长 为r + 1 的路：u 1 p v 一2 v x z v + 尸口，+ l ，矛盾伽”显然若叫v ( g ) ( v ( p ) u x ，y ，z ) ) ，由 n ( y ) ( z ) u ( 一) 及显然w v 岳e ( g ) 知w x e ( g ) 从而u l p w x v p v ，+ 1 为g 中长 为r + 1 的路、矛盾以上矛盾说明引理3 1 1 成立 引理3 1 2 设g 是连通的半无爪图，p = v 1 v 2 v p 是g 中的最长路，z v ( g ) y ( 尸) ，口y ( p ) ，使z u _ e ( g ) ，则a = v j ( 1 ) ，b c = ( ， + ) 两两不交 声( 咋) = ( u + ：u p ( 邯) 证明由引理3 1 1 ，v - 十e ( g ) 因为p 是最长路，所以口隹 口l ，u 2 ，7 2 p _ 1 ，) 若4 n b 西，则存在v i anb ，于是p 上的点构成一个圈口1 p u v p - p v i v l ，而o u e ( g ) ， 易得长于p 的路显然v l 岳a 若”a ，贝l l z v ? 3 1 p v 一口+ 尸是长于p 的路若v + a ， 1 z v p v l v + p v p 是长于p 的路所以anc = 咖显然w 1 车b 若u b ，则 l p v v p p v z 是 长于p 的路，若w + b ，则”】p v 一 十