H-局部连通图的路圈性质

摘要

路和圈是图的两种基本结构,是分析和刻画图的有力工具．有大量的实际问题可以归结为图的路和圈问题．所以这方面一直是图论中的热点研究领域．关于路和圈的进展．已经取得了长足的发展．这方而的研究成果和进展可参见文献[13]-[16]．事实上．图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题．经过几十年的发展．图的路圈性质所涉及的内容日益丰富和具体．路的方面包括图的Hamilton-路(可迹性)．最长路．Hamilton连通．泛连通．路可 1等等：圈的方面包括图的Hamilton圈．最长圈．(点)泛圈．完全圈可扩．点不交的圈．圈覆盖等等． 由于直接研究一般图的Hamilton问题往往比较困难．于是人们转而研究不含有某些禁用子图的图类．继Beinekel968.1970年发表的关于线图性质的两篇文章[17]-[18]之后．人们开始关注包含着线图的无爪图．70年代末80年代初．是研究无爪图的一个非常活跃的时期．关于无爪图方面的部分优秀成果可参考[2]-[4]．[19]-[33]．[34]是关于无爪图的综述性的文章．另外．无爪图的概念也被从不同角度推光到了更大的图类．如半无爪图．几乎无爪图．(K1.4:2)图．DCT图等．1998年．A.Ainouche在[7]中定义了一种包含无爪图的更大图类一半无爪图且给出了关于半无爪图的路和圈方面的一些结果．之后，很多专家学者相继做了大量的工作来研究这类图的Hamilton问题且将无爪图中的许多非常好的结果推广到了半无爪图．其中某些进展可参考[35]-[37]．1994年，Z．Rgjacek定义了一种包含无爪图的更大的图类-几乎无爪图．之后,亦出现了不少研究这类图的Hamilton问题的学术论文如[39]-[41]． 对τ∈ V(G)．若G[N(v)]是连通的,则称v是G的一个局部连通的点．若G的任一点都是局部连通的点．则称G是局部连通的．在局部连通的定义提出之后．张存全在1989年提出了半局部连通的定义，研究了无爪图在半局部连通条件下的一些性质．滕延燕和尤海燕在2002年定义了几乎局部连通．而赖宏建在2004年提出了三角连通的概念，证明了无爪图在三角连通下的一些结果．曲晓英又把这些结果推广到了半无爪图和拟无爪图．我们是在他们的启发下提出的H-局部连通的概念．初步讨论了K2-局部连通下无爪图的一些性质．人们相继又提出了许多不同的相关定义如：几乎局部连通、半局部连通、三角连通、2-阶邻域连通等．H-局部连通图是我们在研究不同图类结构的基础上所提出的一种新的图类。 Zden(e)k．Ry(jac)ek在1997年提出了闭包的概念．并解决了无爪图中的一系列Ha-milton问题．Zden(e)k．Ry(jac)ek所定义的闭包着眼于对局部连通的点的邻域增加边．H．J.Broersma和Tromme]先后又提出了K4-闭包和K*4闭包。RomanCada在2001年提出了C4-闭包和C5-闭包．本文在他们的启发下定义了两种闭包K2-闭包和K2-闭包．并且初步讨论了无爪图和半无爪图在这两种闭包下的一些性质． 本篇论文主要研究了K2-局部连通下无爪图和半无爪图的路和圈问题,以及无爪图和半无爪图在我们定义的两种新闭包下的一些性质． 在第一章中．我们主要介绍了本文的研究背景以及已有的一些结果,以及文章中所涉及的一些概念和术语符号． 在第二章中．我们具体讨论了H-局部连通图的一些性质. 在第三章中,我们研究了K2-局部连通图的圈可扩性,证明了下面的结果: 完成K2-局部连通的无爪图Hamilton性的证明之后．我们开始考虑它的圈可扩性．我们发现这一类图如果满足条件δ≥3，那么完全圈可扩性就成立．于是得到下面的定理． 在第四章中，我们定义了两种闭包：K2-闭包和K′-2-闭包．并证明了下面的结果： 第五章中.我们研究了K14-受限图的圈子可扩性.

目录

声明

第一章预备知识

§1.1符号概念介绍

§1.2研究背景及已有结果

第二章H-局部连通图的性质

第三章K2-局部连通下的无爪图

§3.1 K2-局部连通无爪图的Hamilton性

§3.2 K2-局部连通无爪图的圈可扩性

第四章闭包

§4.1定义

§4.2 K2-闭包

§4.3 K'2-闭包

第五章K1,4-受限图圈可扩性

参考文献

攻读学位期间发表的学术论文

致谢