（应用数学专业论文）图中强路圈性质的若干充分条件.pdf

【l 农师范火学硕士学毖论文 图中强路固性质的若干充分条件 程建民 ( 山东师范大学数学科学学院济南，山东，2 5 0 0 1 4 ) 中文摘要 图的路和圈问题是图论中个十分重要而且活跃的研究课题，有大量的实际问 题可以归结为图的路和圈问题图论中三大著名难题之一的h a m i l t o n 问题本质上 也是图的路和圈问题国内外许多学者对此问题作了大量的研究工作这方面的研 究成果和进展可参见文献f 3 s 一 4 2 1 其中度条件和邻域并条件成为研究路和圈问题 的重要途径，在这方面取得了很多优秀的成果经过几十年的发展，图的路圈性质所 涉及的内容日益丰富和具体路的方面包括图的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 7 0 年发表的关于线图性质的文章【1 7 之后， 人们开始关注包含着线图的无爪图7 0 年代末8 0 年代初，是研究无爪图的一个非 常活跃的时期关于无爪图方面的部分优秀成果可参考【1 】【3 ，【1 9 】- 【3 1j 另外，无爪 图的概念也被从不同角度推广到了更大的图类，半无爪图，几乎无爪图，( k 1 ，4 ；2 ) 一图 等2 0 0 5 年，刘春房在【4 】中定义了一种新的图类_ 【s ，t 卜图，即任意s 个点之间至 少含有t 条边而我在这类b 牛图的基础上提出了强一【s ，t 图，即任意s 个点之间 至少含有t 条独立边这类图的特点是其边的分布比较均匀，因而在交通网络，通信 系统，计算机的网络配置等方面有着很典型的应用 本文就是研究强一 s t 图和一般图中与度有关的强路圈性质 在第一章中，我们主要介绍文章中所涉及的一些概念和术语符号，以及本文的 研究背景和已有的一些结果 在第二章中，我们主要研究了强一【s ，t 】图在不同条件下的强路圈性质，得到下面 的结果： 定理2 1 4 设g 是n ( n 6 ) 阶强一【4 ，2 】图，则g 是泛圈的 定理2 1 5 设g 是n ( n 7 ) 阶强一【4 ，2 】图，则g 是完全圈可扩的 1 山东师范大学硕：t 学位论文 定理2 1 6 设g 是7 1 ( r 1 三= 8 ) 阶强一【4 ：2 】图，则g 是路可扩的 定理2 2 4 设g 是n ( n28 ) 阶连通强一f 5 ，2 j 图，则g 含有h a m i l t o n 路 定理2 2 5 设g 是6 ( g ) 3 的连通? 局部连通的强- 【5 ，2 】图，则c 是完全圈 可扩的或者同构于图p 推论2 2 6 设g 是d ( g ) 芝3 的 8 ) 阶连通，局部连通的强一 5 ，2 】图，则 g 是完全圈可扩的 定理2 3 3 设g 是n ( n 3 m 一1 ) 阶强一 2 m ，叫图，则g 含有h a m i l t o n 路 定理2 3 4 设g 是n ( n23 m ) 阶强 2 m ，叫图，则g 含有h a m i l t o n 圈 在第三章中，讨论了图中在与度有关的条件下关于圈的几个结果： 定理3 8 设g 的阶礼3 ，如果g 中任意一对不相邻的顶点u ， 满足d ( u ) - 4 - d ( v ) 礼+ 惫，则g 中任意个满足彘 l c l 钆的圈c 是- - f 扩g j 推论3 9 设g 的阶t t 3 ，如果g 中任意一对不相邻的顶点钍，u 满足d ( u ) + d ( v ) 之i 佗一2 ，则g 是完全圈可扩的 定理3 1 0 设g 的阶讥3 ，如果g 中任意一对d ( 牡，t ，) = 2 的顶点札，t ，满足 d ( u ) + d ( v ) 礼+ 1 ，则存在个顶点z 仙，u ) ，过z 有各种长度的圈 在第四章中，讨论了图中在与度有关的条件下关于路的几个结果： 定理4 3 设g 的阶n 3 ，如果g 中任意一对不同的顶点 l t ，u 满足d ( u ) + d ( v ) 礼+ l ，则g 是路可扩的 定理4 4 设g 的阶n 3 ，如果g 中任意一对不相邻的顶点u ，u 满足d ( u ) + d ( v ) 2n + 1 ，则g 中任意一条满足詈+ 1 l p l 礼的路p 可扩的 关键词：强一【s ，t 】图；路可扩；泛圈；完全圈可扩 分类号：0 1 5 7 5 2 山东师范大学硕士学位论文 s o m es u f f i c i e n tc o n d i t i o n so fs t r o n gp a t h sa n d c y c l e sp r o p e r t yi ng 1 a p h s j i a n m i nc h e 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 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 y i m p o r t a n tp r o b l e mi n g r a p ht h e o r ya n dt h er e s e a r c hi s a l s oa c t i v e 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 w h a ti sm o r e ，t h ef a m o u sh a m i l t o n p r o b l e mb e l o n g st 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 y s c h o l a r sa th o m ea n da b r o a dm a d eal o to f r e s e a r c hw o r ko nt h i si 8 8 u e t h er e s e a r c h r e s u l t sa n dp r o g r e s si nt h i sa r e ac a nb ef o u n di nl i t e r a t u r e 3 8 一【4 2 】t h ec o n d i t i o no f d e g r e ea n dn e i g h b o r h o o du n i o n sb e c o m e s a 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 sr e s p e c t ，al o 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 f t e rt h ed e v e l 一 o p m e n tf o rd o z e n so fy 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 dc y c l e b e c o m em o r ea n dm 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 n p 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 d8 0o n ； t h ep r o p e r t i e so fc y c l ei 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 w e v e r w ec a nn o td e n yt h ef a c tt h a ti t i su s u a l l yv e r yd i f i 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 r nt oe x p l o r e t 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 sc l a w - f l e eg r a p h s t h e f 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 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 17 h o w e v e r ，t h em a i ni m p u l s e t 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 fc l a w - f l e e g 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 eg r a p h sc a nb es e e ni n 【1 】_ 【3 】，【1 9 】 3 1 】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 l 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 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 h 3 山东师范大学砺 学位论文 a sq u a s i - 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 ，( k i 。4 ；2 ) - g r a p h se t c i n2 0 0 5 l i uc h u n f a n g 【4 】d e f i n e dan e wg r a p hf a m i l 3 卜g r a p h s ，t h a ti s ，t h e r ea l ea t l e a s tte d g e si ne v e r yi n c l u d e ds u b g r a p h so fsv e r t i c e si ng r a p hg a c c o r d i n gt o t h i sg r a p h ，id e f i n e dan e wg r a p hf a m i l y s t r o n g ，t g r a p h s ：t h a ti s ，t h e r ea r ea t l e a s tfi n d e p e n d e n te d g e si ne v e r yi n c l u d e ds u b g r a p h so fsv e r t i c e si ng r a p hg t h e s eg r a p h sc a nb eu s e di nt r a f f i cn e t w o r k ，c o m m u n i c a t i o n s ，t h ec o n f i g u r a t i o no f c o m p u t e rn e t w o r k s ，e t c i n t h i sp a p e r ，w em a i n l yd i s c u s st h ep r o p e r t i e so fg r a p h s p a t ha n dc y c l ei n 【s j 小g r a p h sa n dt h ep r o p e r t i e sa b o u td e g r e eo fg r a p h s p a t ha n dc y c l ei na l lg 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 o l 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 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 y g 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 ： s t u d yt h ep a t h sa n dc y c l e so fs t r o n g 一【s it 】 t h e o r e m 2 1 4i fgi sas t r o n g - 4 ，2 】g r a p hw i t hj g i 6 ，t h e ngi sp a n c y c l i c t h e o r e m 2 1 5i fgi sas t r o n g 一 4 ，2 】g r a p hw i t hi g l 7 ，t h e ngi sf u l l yc y c l e e x t e n d a b l e t h e o r e m 2 1 6i fgi sas t r o n g 一 4 ，2 】g r a p hw i t hl g l 8 ，t h e ng i sp a t h e x t e n d a b l e t h e o r e m 2 2 4i fgi sac o n n e c t e ds t r o n g 一【5 ，2 】g r a p hw i t hl g f 8 ，t h e ng h a sah a m i l t o np a t h t h e o r e m 2 2 5i fgi sac o n n e c t e d ，l o c a lc o n n e c t e ds t r o n g - j 5 ，2 g r a p hw i t h i g i 8a n d6 ( c ) 3 ，t h e ng i sf u l l yc y c l ee x t e n d a b l eo rg 垒f c o r o l l a r y 2 2 6 i fgi sac o n n e c t e d ，l o c a lc o n n e c t e ds t r o n g 一【5 ，2 】g r a p hw i t h i gj 8a n d6 ( g ) 3 ，t h e ng i sf u l l yc y c l ee x t e n d a b l e t h e o r e m 2 3 3i fg i sa s t r o n g - 2 m ，7 司g r a p hw i t hi g i 3 m 一1 , t h e ng h a s ah a m i l t o np a t h 4 山东师范大学硕士学位论文 t h e o r e m 2 3 4i fgi sas t r o n g 一 2 m ，7 n 】g r a p hw i t hi g i 3 m ，t h e ngh a sa h ( t , l v i l t o , tc y c l e i nt h et h i r dc h a p t e r ，w em a i n l ys t u d yc y c l e so fa l lg r a p h sa b o u td e g r e ec o n d i t i o n 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 m 3 8l e tgb eag r a p ho fo r d e rn 3 i fd ( u ) + d ( u ) n + kf o re v e r y p a i r i t ，vo fn o n a d j a c e n tv e r t i c e s ：t h e nt h ee v e r yc y c l ecs a t i s f y i n g 南 l c i 礼 i se x t e n d a b l e c o r o l l a r y 3 9l e tgb eag r a p ho fo r d e r 咒23 i fd ( u ) + d ( v ) 挚一2f o r e v e r yp a i ru ，uo fn o n a d j a c e n tv e r t i c e s ：t h e ng i sf u l l yc y c l ee x t e n d a b l e t h e o r e m 3 1 0l e tgb ea g r a p ho r d e rn 3 i f d ( u ) + d ( u ) 2n + 1f o re v e r y p a i rt 正iuo fd ( u ，口) = 2 ，t h e ne x i s t i n gav e r t e xz 【仳，口】a n de a c hi n t e g e r 后w i t h 3 k n ，gh a sak - c y c l eg s u c ht h a tz y ( 仉) i nt h ef o u r t hc h a p t e r ，w em a i n l ys t u d yp a t h so fa l lg r a p h sa b o u td e g r e ec o n - d i t i o n 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 m 4 3l e tgb eag r a p ho fo r d e rn 3 i fd ( 札) + d ( v ) n + 1f o r e v e r yp a i r 化，v ，t h e ng i sp a t he x t e n d a b l e t h e o r e m 4 4l e tgb eag r a p ho fo r d e rn 3 i fd ( u ) + d ( ) 礼+ 1f o re v e r y p a i ru ， o fn o n a d j a c e n tv e r t i c e s ，t h e nt h ee v e r yp a t h 尸s a t i s f y i n g 号4 - 1 l p i n j se x t e n d a b l e a b l e k e y w o r d s ：s t r o n g i s ，t 】g r a p h s ；p a t he x t e n d a b l e ；p a n c y c l i c ；f u l l yc y c l ee x t e n d - c l a s s i f i c a t i o n ：0 1 5 7 5 5 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 ( 注：如没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或 证书使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意 学位论文作者签名： 锃建瓦 导师签名： 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅 和借阅本人授权学校可以将学位论文的全部或部分内容编入有关数据库 进行搜索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密的学位论文在解密后使用本授权书) 学位论文作者貅程建瓦 导师躲 签字日期：2 0 0 9 年妒月r 日签字日期：2 0 0 9 年阳，日 山东师范大学硕士学位沦文 第一章预备知识 1 1研究背景 图的h a m i l t o n 性是图论研究中的热点问题之一一百多年前，爱尔兰数学家 哈密尔顿提出了这样一个问题：一个连通图有i l a m i l t e m 圈的充分必要条件是什 么? 这就是著名的哈密尔顿问题该问题一经提出就受到广泛关注，后经研究发现 它是个n p c 问题 对图的路圈性质的研究是以哈密尔顿问题为起点发展起来的，相关的研究主要 集中在两个方面，是寻找图具有某些路圈性质的充分条件，二是研究某些特殊图 类的路圈性质后者中的特殊图类主要是指不含某些特定结构的导出子图的图类， 这些特定结构的导出子图又称作禁用子图无爪图就是以甄3 为禁用子图的图类 由于其深刻的研究背景一一线图都是无爪图，上个世纪的七八十年代无爪图受到图 论界的广泛关注，对无爪图的路圈性质的研究也是在这个时期开始的 经过几十年的发展，图的路圈性质所涉及的内容日益丰富和具体比较常见 的路的方面有可迹性，h a m i l t o n 连通，泛连通性，路可扩性等，圈的方面有哈密顿 圈，( 点) 泛圈性，完全圈可扩性等同时从无爪图的禁用子图硒3 的结构出发，又相 继定义了些新的图类，如几乎无爪图，半无爪图，( k 1 ，p ；q ) - 图等等一方面人们尝 试把无爪图中的结论推广到更大的图类，另方面人们也希望得到这些新的图类在 路圈方面的一些新的结果 基于以上研究背景，本文选择了强一【5 ，t 】图以及一般图中与度有关的路圈性质 作为研究的内容，主要沿着推广已有结论和探索新结果两个思路进行研究 6 山尔师范大学硕士学位论文 1 2符号概念介绍 本文仅考虑有限无向简单图，所使用的记号和术语约定如下，其中未加说明的 部分请参照文献 4 7 】 设g 是一个图，y ( g ) ：e ( c ) 分别表示g 的顶点集和边集对于v y ( g ) ， s ，t ，b ，f y ( g ) ，令 n ( v ) = u v ( c ) ：删e ( g ) 】- ，n v 】= n ( v ) u u ) n b ( u ) = n ( v ) nb ，n 8 ( f ) = un s ( ”) 劬， e ( s ，t ) = f s t e ( c ) ：5 st t 】 图g 的由s 导出的子图记为g 将图g 中与t ，关联的边的数目叫做顶点 ”的度，记为d c ( v ) ，即d c ( v ) = i ( 可) l ，在不引起混淆的前提下也简记为d ( u ) 用 如，g 分别表示g 中顶点的最小度和最大度，也常简记为6 ， 如果图g 中不存在k 一1 个顶点的集合分离g ，则称g 是k 一连通的，图g 的连通度t ( c ) = m a x k ：g 是k 一连通的) 若对任意t ，y ( g ) ，g 【( 口) 】是连通 的，则称图g 是局部连通的 以g 中顶点z ，y 为端点的路记为( z ，) 一路g 中最短( z ，y ) 一路的长，称为z 和y 间的距离，记为d ( z ，可) 恶琵以( t ，y ) 称为图g 的直径 设p = x l x 2 z t 为图g 的一条路，z i ，x j y ( 尸) ( 1 i j t ) ，用 z f 2 和z 分别表示尸上的点x i f 和z 件f ，其中z 产1 ，z 产2 和z f l ，z _ 2 也分别记为 ：i 专一：+ 和：c i ，z i 一；甩x i p ：r j 积z 尹z t 0 j 、) 分磊也表示p 的子路z t z t + l a ：j 积 t j z j 一1 z t 设c = u 1 忱坼u l 是图g 中的圈，饥，v j y ( c ) ( 1 i j 7 ) ，用町。和 t 矿2 分别表示c 上的点协一z 和 u i + f ，其中矿1 ，时2 和町1 ，町2 也分别记为时，矿+ 7 山东师范大学硕士学位论文 和1 f ，町一；用? 心口和，如虿吩分别表示c 上的路， 耽+ 1 功和饥一1 t ( 这里 点的下标均模r ) 经过g 中每个顶点恰好一次的路( 圈) 称为( g 的) h a m i l t o n 路( 圈) 若g 中存在一个h a m i l t o n 圈，则称g 是哈密尔顿的令f y ( a ) i = n ，若对于任意的 1 ( 3 f 礼) ，g 中都有长为f 的圈，则称g 是泛圈的对于g 中任意的顶点石及任 意满足3 f n 的整数z ，都存在经过z 的长度为f 的圈，则称g 是点泛圈的如果 图g 满足：( 1 ) g 的每个顶点都在长度为3 的圈上；( 2 ) 对g 中任意个圈c ，只要 i y ( c ) l f v ( o ) l ，就存在g 的圈，使得v ( c ) cv ( c 7 ) 且f v ( c ，) f = f y ( g ) f + 1 ， 则称g 是完全圈可扩的，c 称为c 的扩圈 如果对于g 中任意两个顶点z ，y ，都存在以，y 为端点的h a m i l t o n 路，那 么称图g 为h a m i l t o n 一连通的如果图g 满足：对任意的仳，v v ( a ) 及g 的 任意一条( 乱，u ) 一路p ，只要l y ( 尸) l i v ( c ) l ，就存在g 的( u ，口) - 路p ，使得 v ( p ) cv ( p 7 ) 且l v ( p ，) i = i y ( p ) i + l ，则称g 是路可扩的满足条件的p 7 叫做 p 的扩路 如果图g 中任意s 个点的导出子图中至少含有t 条边，则称图g 为【s ，t 】图 由【s ，t 卜图的定义容易知道， s ，小因有下述性质： 性质1bt 卜图是【s ，t 一1 1 一图 性质2 【s ，t 】- 图是【s + 1 ，小图 性质3 【s ，小图是 5 + 1 ，t + 1 1 一图 性质4 设g 是 s ，t 卜图，对g 任意子图，如果j hj s ，则h 是kt l 一图 如果图g 中任意s 个点的导出子图中至少含有t 条独立边，则称图g 为强 一【s ，t 】图 由强一【s ，t 】图的定义容易知道，强一【s ，t 】图有下述性质： 8 山东师范大学硕士学位论文 图 性质5 强一h 图是强 s ：t 一1 】图 性质6 强一i s ，t 图是强一【5 + l ，t 图 性质7 设g 是强一【s ，t 】图，对g 任意子图日，如果l h i s ，则h 是强一【s ，t 】 1 3已有结果 2 0 0 5 年，刘春房，王江鲁【4 】给出k 小图的定义及下面的结果： 定理2 1 1 【4 l 设g 是 4 ；2 卜图，则 ( a ) g 是连通的当且仅当g 同构于k a ，3 或者g 有h a m i l t o n 路 ( b ) g 是2 - 连通的当且仅当g 同构于恐，3 或者g 同构于k x ，1 ，3 或g 有 h a m i l t o n 圈 2 0 0 7 年，雷泓昊，李敏等f 4 4 】，【5 0 给出下面结果： 定理2 1 2 1 4 4 1 设g 是连通，局部2 一连通的 4 ，2 1 图，则g 或者含有与k 1 ，1 ，3 同构的子图，或者是路可扩的 定理2 2 1 【5 0 l 设g 是2 连通【5 ，2 卜图，则g 同构于鲍，4 或g 含有h a m i l t o n 路 2 0 0 6 年，蔺厚元孔淑霞 5 】给出下面结果： 定理2 2 2 【5 】设g 是3 连通 5 ，3 卜图，则g 有h a m i l t o n 圈或者g 全面v 岛 2 0 0 6 年，李敏【4 5 给出下面结果： 定理2 2 3 【4 5 j 设g 是n ( n27 ) 阶连通【5 ，3 卜图，则g 中最长圈的长度不小 于【n 2 j ，此界是最好可能的 2 0 0 3 年，尤海燕【4 8 证明了几个关于( 硒，4 ；2 ) - 图在路方面的结果： 9 定理2 3 1 【4 8 l 设g 为连通的( k 1 ，4 ；2 ) - 图，j g i 7 则g 有哈密尔顿路或有 长至少为2 6 + 2 的路 定理2 3 2 1 4 8 1 设g 为连通的( k x ，4 ；2 ) - 图，l g l 7 ，c i 翌手，则g 有哈密尔 顿路 1 9 5 2 年，g a d i r a c 1 3 】得到如下结果： 定理3 1 【1 3 】设图g 的阶佗3 ，如果6 ( g ) 詈，则g 有h a m i l t o n 圈 1 9 6 0 年，0 o r e 1 4 】改进上述结果，得到如下结果： 定理3 2 1 4 1 设图g 的阶礼3 ，如果g 中任意对不相邻的顶点u ，v 满足 d ( u ) + d ( v ) n ，则g 有h a m i l t o n 圈 1 9 8 4 年，范更华1 1 8 】给出了如下定理： 定理3 3 【1 8 】设图g 是n 阶2 连通图，对任意两个顶点u ，t ，如果d ( “，u ) = 2 号m a x ( d ( u ) ，d ( t ，) ) 号，则g 是h a m i l t o n 的 1 9 9 0 年，g r t h e n d r y 7 在无爪图中给出了下面关于完全圈可扩的结论： 定理3 4 1 7 1 顶点数不小于3 的连通，局部连通无爪图是完全圈可扩的 1 9 9 4 年，冗y j h s e k 3 6 】将定理4 1 推广到几乎无爪图得到： 定理3 5 【3 6 j 顶点数不小于3 的连通，局部连通的几乎无爪图g 中，如果不含 与所4 同构的导出子图，则g 是完全圈可扩的 1 9 9 0 年，g r t h e n d r y 7 发现已有的一些保证h a m i l t o n 圈存在的度型充分 条件实际上隐含着圈可扩性，并得到了如下结果： 定理3 6 n 设图g 的阶礼23 ，如果6 ( g ) 孚，则g 是完全圈可扩的 1 9 8 6 年，田丰、施容华【4 6 】给出了如下定理： 1 0 定理3 7 ( 4 6 】设图g 是n 阶2 - 连通图，对任意两个顶点如果d ( u ，f i ) = 2 穹m a x ( d ( u ) ，d ( f 们之可n + l ；则g 是泛圈的 1 9 9 7 年，王江鲁，朱永津等【6 1 在几乎局部连通条件下证明了： 定理4 1 【6 】连通，局部2 连通的无爪图是路可扩的其中，局部2 一连通条件是 不能降的 2 0 0 3 年，尤海燕【4 8 】证明了下面的结果： 定理4 2 【4 8 j 连通，局部3 - 连通的( 凰，4 ；2 ) - 图是路可扩的并且指出其中的 局部连通度条件是最好可能的 山东师范大学硕士学位论文 第二章强一 s ，】图的强路圈性质 这一章主要研究强一【s ，t 】图在各种条件下的路和圈的性质 2 1强【4 ，2 1 图的路圈性质 刘春房最早在2 0 0 5 年提出【s ，t 卜图的概念f 4 l ：如果g 中任意s 个顶点的导 出子图中至少含有t 条边，则称图g 为【s ，小图我在此基础上提出强一i s ，t 】图的 概念：如果g 中任意5 个顶点的导出子图中至少含有t 条独立边，则称图g 为强 一i s ，t 】图强- s ，t 】图是对卜，小图的种延伸强一【4 ，2 】图即指g 中任意4 个点的 导出子图中至少含有2 条独立边。 引理2 1 3n 阶强一 2 m ，m j 图g 为( n 一2 m ) 一连通的 证明：否则，图g 中存在礼一2 m 一1 个点的顶点割s ，因为i g s l = 2 m + 1 为奇数，所以在g s 中存在分支h l 含有k 个点，其中k 为奇数，于是日l 中至多 含有生条独立边再在剩余的2 m k + 1 个点中任意选取2 m k 个点的集合 z 毛，显然2 m k 为奇数，所以凰的导出子图中至多含有2 m 下- k 一- 1 条独立边又因 为何j 中的点与肌中的点无边相连，所以g h 1uh 2 1 中至多含m 一1 条独立边， 矛盾于性质7 定理2 1 4 设g 是n ( n 6 ) 阶强一【4 ，2 】图，则g 是泛圈的 定理中n 6 的条件是必要的，岛即是一个反例 论断1 ：设w = z ，y ，z ) cy ( g ) ，则 ( a ) e ( g 【1 ) 毋； ( b ) vv v ( c ) 一，v w ( ) o 证明：若( a ) 或( b ) 不成立，则g ( z ，z ， ) 】中至多有一条独立边，与g 是强 一 4 ：2 】图矛盾，论断1 证完 1 2 山东师范大学硕士学位论文 论断2 ：设t ，y ( c ! ) ：若d ( v ) 3 ，则u 在g 的一个长为3 的圈上 证明：取w = z ：y ，z cj 7 v ( t ，) ，由论断1 ( o ) ，e ( g w 】) d ，不妨设x y e ( g ) ， 则x y v x 就是g 中过定点v 的3 囤论断2 证完 因为n 6 ：由定理4 ，g 为2 连通的，所以6 之2 此时必有a 3 ( 否则g 是 一个佗圈，设g = v l u 2 v n v l ，取u = v i ，v 3 ，u 5 】，则e ( g 【己1 ) = 谚，与论断l ( a ) 矛盾) ，由论断2 ，g 有长为3 的圈 设c 是g 的一个圈且l y ( c ) l j v ( g ) i ，以下假设g 中不含长为l c l + 1 的 圈令 r = v ( c ) 一y ( g ) ，t = w e ( r ) ，e ( r ，t ) = z 可6e ：z r ，y 丁 当i y ( c ) i = 3 时，记c = v l v 2 u 3 y l ，因为l gj 6 ，且g 为2 一连通的，所以 i t l 2 情形1 i t i = 2 不妨记t = u l ，忱】，因为y ( g ) i i y ( c ) l 3 ，取k = x ，y ，z ) r ，由 论断1 ，z ，y ，z 中每个顶点必与c 中其中个顶点相邻，所以存在w t ，使 坛( 训) 2 ，不妨记w = u 1 且7 2 1 x ，v l y e ( r ，t ) ，所以x v 2 ，秒也，x v a ：y v 3 簪e ，又 因为v 2 t ，所以存在点s ，使s v 2 e ，因为g b ，z ，y ，s 】为强一 4 ，2 】图，所以1 1 3 与z ，y ，s 其中之一相邻，所以y 3 s e ( g ) ，可得i j l v 2 8 v 3 v l 为扩圈 情形2 i t i = 3 此时t = v 1 ，v 2 ，v 3 ，则存在y l ，y 2 ，y 3 ，使v l y l ，v 2 y 2 ，v 3 y 3 e ( r ，丁) ，若 y 1 ，y 2 ，y 3 中有2 点重合：则可得扩圈若1 ，y 2 ，y 3 均不重合，则g m ，y 2 ，珈，v 3 】为强 一【4 ，2 】图，又因为v 3 y l ，v 3 y 2 芒e ( g ) ，所以y l y 2 e ( g ) ，可得v l y x y 2 v 2 v 3 v l 是长度为 4 的圈 当i y ( c ) f 4 时，记g = v l y 2 v k v l 由引理2 1 3 可知，i t i 2 ，所以存在 y r ，使y i y6e ( g ) ，因为c y ，町，矿，时2 】为强一 4 ，2 】图，且y v ? ，y v t 盛e ( g ) ， 所以讨2 ，町讨e ；可得y v + 2 c 町时甄为扩圈，矛盾 1 3 山东i i i l i 范大学硕士! 学位论文 综上，定理2 1 4 得证 定理2 1 5 设g 是n ( n27 ) 阶强一【4 ，2 】图，则g 是完全圈可扩的 定理中竹7 的条件是必要的 证明：因为钆71 所以由引理2 1 3 可知，图g 是3 连通的，所以6 3 ，则对 任意顶点2 ，有d ( 口) 3 ，由论断2 可知，秒在g 的个长为3 的固上 设c 是g 的个圈，且i y ( c ) l i y ( g 1 ) i ，以下假定c 没有扩圈令 r = v ( a ) 一y ( c ) ，t = n c ( 冗) ，e ( r ，即= z e ：z r ，y 丁) 当i y ( c ) i = 3 时，记c = v l v 2 v 3 v l ，因为i g l 7 ，且g 为3 连通的，所 以i t l23 又因为f y ( c ) i = 3 ，所以l tj = 3 不妨记t = 1 ， 0 2 ，啦) ，因为 j y ( g ) i i y ( c ) i24 ，取k = x l ，x 2 ，x 3 ，z 4 ) r ，由论断1 ，k 中每个顶点必 与g 中其中个顶点相邻，所以存在w t ，使 k ( 叫) 2 ，不妨记伽= v l 且 u l z l ，v l x 2 e ( r ，丁) ，所以x l v 2 ，x 2 v 2 ，t l v 3 ，x 2 y 3 萑e ，又因为忱t ，所以存在点 x 3 ，使x a v 2 e ，因为g v 3 ，z l ，x 2 ，z 3 】为强一【4 ，2 1 图，所以i ) 3 与z l ，x 2 ，x 3 其中之一 相邻，所以u 3 x 3 e ( g ) ，可得u lv 2 x 3 y 3 y l 为扩圈 当i y ( c ) i 4 时，记c = v l _ t 1 2 u k 郇1 由引理2 1 3 可知，i t i 3 ，所以存在 y r ，使v i y e ( g ) ，因为g 阿， f ，讨， 产2 】为强一【4 ，2 】图，且可町，! ，u 产萑e ( g ) ， 所以y , 4 - 2 ，町访e ，可得y v ? 2 c 町时观为扩圈，矛盾 综上，定理2 1 5 得证 定理2 1 6 设g 是n ( 佗8 ) 阶强一 4 ，2 】图，则g 是路可扩的 定理中n 8 的条件是必要的 证明：设p = v l u 2 咋是g 中一条满足2 p 4 ， 帆( u 1 ) nl v x ( v 2 ) d 设u 坛( 1 ) n 以( 沈) ，则u 1 y y 2 为，的扩路 情形2