论文部分内容阅读
图的哈密顿问题是图论学科一个十分重要而且又十分活跃的研究课题,历史也很悠久,每年都有大量关于这一问题的学术论文.但是,由于直接研究一般图类的哈密顿问题比较困难,因此,当前,图的哈密顿问题研究的一个重要方面是在一些特定领域展开.关于哈密顿问题的一些研究进展可参考[23]-[25].继Beineke1968,1970年发表的[10]-[11]之后,人们开始关注起包含着线图的无爪图.70年代末80年代初,是研究无爪图的一个非常活跃的时期,这一时期,涌现了大量优秀的成果.其中,关于匹配性质的可参考[12]-[14].较早关于无爪图哈密顿性质的可参考[15]-[18].关于多项式时间内确定独立数的可参考[19][20].关于Berge的完美图猜想在无爪图中的证明可参考[21].[22]是关于无爪图的综述性的文章,从中我们可了解到关于无爪图的研究进程.另外关于无爪图中取得的优秀成果的文章可参考[37]-[50].事实上,可迹性,泛圈性,完全圈可扩性,哈密顿连通等这些之后提出的概念本质上都是对图的哈密顿问题的深层次的刻画.
最近若干年来,无爪图的概念也被从不同角度推广到了一些更大的图类,如:半无爪图,几乎无爪图,(K1,4;2)-图,DCT图等.其中,关于半无爪图的一些研究进展可参考[3],[26]-[28],关于几乎无爪图的可参考文献[29]-[32],关于(K1,4;2)-图的可参考[33]-[35].拟无爪图是滕延燕,尤海燕2004年基于几乎无爪图在[6]中提出来的,它也是对无爪图概念的一种推广,但它却包含在几乎无爪图类中,然而,很多在几乎无爪图中很难研究的东西在拟无爪图中却比较容易找到方法来研究.(V)独立集{x1,x2,…,xp}(∈)V(G)(p≥2),如果N(x1)∩N(x2)∩…N(xp)≠φ,那么若(V)u∈N(x1)∩N(x2)∩…N(xp),有N[u](∈)N[x1]∪N[x2]∪N[xp],则称u为{x1,x2,…,xp}的控制点.否则,称u为{x1,x2,…,xp}的非控制点.{x1,x2,…,xp}的控制点组成的集合称为{x1,x2,…,xp}的控制集,记为D(x1,x2,…,xp);{x1,x2,…,xp}的非控制点组成的集合称为{x1,x2,…,xp}的非控制集,记为(D)(x1,x2,…,xp).(V)独立集{x1,x2,…,xp}(∈)V(G)(p≥2),如果N(x1)∩N(x2)∩…N(xp)≠φ,那么D(x1,x2,…,xp)≠φ,且若(V)u∈D(x1,x2,…,xp),(V)v∈(D)(x1,x2,…,xp),有uv∈E(G),则称G为K1,p-扩展图.由定义不难知道K1,p1-free图一定是K1,p-扩展图.特别地,K1,3-free图一定是K1,2-扩展图.即易知K1,2-扩展图也是对无爪图的一种推广.这类图是我们在对图的结构进行深入研究的基础上提出来的.
本篇论文中,我们主要研究了拟无爪图的点泛圈性和不同连通条件下K1,2-扩展图的完全圈可扩性.
在第一章中,我们主要介绍了文章中所涉及的一些概念,术语符号和本文的研究背景以及已有的一些结果.
在第二章中,我们主要研究了拟无爪图的点泛圈性,证明了下面两个结果:定理2.2.3设G是连通的拟无爪图且δ(G)≥3,若G中同构于Z1的导出子图有性质φZ1(c,b1)或φz1(c,b2),则G是点泛圈的(其中Z1如图2.1中的图).
定理2.3.3设G是2-连通的拟无爪图且δ(G)≥3,若G中同构于Z2的导出子图有性质φZ2(a1,b1)和φZ2(a1,b2),则G是点泛圈的(其中Z2如图2.2中的图).
事实上,以上两个结果分别改进了H.J.Broersma,H.J.Veldman[36],MingchuLi[2]等人的相应结果.
在第三章中,我们探讨了不同条件下K1,2-扩展图的完全圈可扩性,改进了D.Oberly,D.Sumner[7],L.Clark[8]以及G.R.T.Hendry[9]的相应结果.得到了下面的三个定理:定理3.2.1设G是顶点数不小于3的连通的K1,2-扩展图,C为G中一r-圈(3≤r<|V(G)|).若G有一桥B,使得NC(B)中含局部连通的点,则G中含C的扩圈.
定理3.3.4顶点数不小于3的半局部连通的K1,2-扩展图是完全圈可扩的.
定理3.4.1顶点数不小于3的连通几乎局部连通的K1,2-扩展图G,若满足δ(G)≥3,则G是完全圈可扩的.且其中δ(G)的下界是最好可能的.