论文部分内容阅读
路和圈是图的两种基本结构，是分析和刻画图的有力工具，有大量的实际问题可以归结为图的路和圈问题，所以这方面一直是图论中的热点研究领域.事实上，图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题.最近若干年来，这方面的研究主要集中在图的Hamilton性，泛圈，点泛圈，圈可扩，最长圈，Hamilton连通，路可扩，最长路等性质的研究上而且已经取得了长足的进展.由于直接研究一般图的Hamilton问题往往比较困难，于是人们转而研究不含有某些禁用子图的图类.继Beineke1968，1970年发表的关于线图性质的两篇文章[17]-[18]之后，人们开始关注包含着线图的无爪图.70年代末80年代初，是研究无爪图的一个非常活跃的时期.关于无爪图方面的部分优秀成果可参考[2]-[4]，[19]-[33].[34]是关于无爪图的综述性的文章.另外，无爪图的概念也被从不同角度推广到了更大的图类，如半无爪图，几乎无爪图，(K1，4；2)-图，DCT图等.1998年，A.Ainouche在[7]中定义了一种包含无爪图的更大的图类-半无爪图且给出了关于半无爪图的路和圈方面的一些结果.之后，很多专家学者相继做了大量工作来研究这类图的Hamilton问题且将无爪图中的许多非常好的结果推广到了半无爪图.其中，某些进展可参考[35]-[37].1994年，Z.Ryjácek[38]定义了一种包含无爪图的更大的图类-几乎无爪图.之后，亦出现了不少研究这类图的Hamilton问题的学术论文如[39]-[41].但事实上，无爪图中许多很好的结果要推广到几乎无爪图难度非常大.所以，滕延燕，尤海燕2003年[5]在此基础上提出了拟无爪图的概念，它包含无爪图类但却包含在几乎无爪图类中.但是，在这个概念下，很多至今还没有能够推广到几乎无爪图的无爪图中的非常好的结果却可以推广到拟无爪图.K1,p-扩展图是我们在研究不同图类结构的基础上所提出的一种包含K1,p+1-free图的新的图类.(A)独立集{x1，x2，…，xp}(∈)V(G)(p≥2)，如果N(x1)∩N(x2)∩…N(xp)≠φ，那么若(A)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).(A)独立集{x1，x2，…，xp}(∈)V(G)(p≥2)，如果N(x1)∩N(x2)∩…N(xp)≠φ，那么D(x1,x2，…，xp)≠φ，且若(A)u∈D(x1，x2，…，xp)，(A)v∈-D(x1，x2，…，xp)，有uv∈E(G)，则称G为K1,p-扩展图.特别地,K1,2-扩展图类是包含着无爪图类且比无爪图类更大的图类.本篇论文主要研究了无爪图，半无爪图，拟无爪图，K1,p-扩展图的路和圈问题.
在第一章中，我们主要介绍了文章中所涉及的一些概念，术语符号和本文的研究背景以及已有的一些结果.
在第二章中，我们通过具体实例讨论了关于无爪图的已有的在不同连通条件下的几个结果间的关系，证明了下面的结果：
定理2.5无孤立点的三角连通的无爪图也是半局部连通的.
推论2.6”边数不小于3的三角连通的无爪图是点泛圈的”这个结果包含在”顶点数不小于3的半局部连通的无爪图是点泛圈的”这个结果中.
在第三章中，我们探讨了半无爪图的最长路，点泛圈性以及闭包等问题，进一步改进了M.Malthews,P.Sumner,R.J.Faudree，HongjianLai,C.Q.Zhang等人的相应结果.
定理3.1.3连通半无爪图G有Hamilton路或有长至少为2δ(G)+2的路.
定理3.1.4设G为连通半无爪图，若δ(G)≥(|G|-2)/3，则G有Hamilton路.
定理3.4.2边数不小于3无孤立点的三角连通半无爪图是点泛圈的.
定理3.5.4顶点数不小于3的半局部连通的半无爪图是点泛圈的.
定理3.5.5设G是连通度κ(G)≥2的半无爪图，M(G)={x∈V(G)：〈N(x)〉连通}，M(G)是G的控制集且〈M(G)〉有r个连通分支，若r≤κ(G)，则G是Hamilton图.其中κ(G)的下界r是最好可能的且G不一定是泛圈的.
定理3.6.1顶点数不小于3的连通几乎局部连通半无爪图G若满足δ(G)≥3，则G是点泛圈的且其中δ(G)的下界是最好可能的.
定理3.7.1若G是半无爪图，x是G的一适宜点，G为由G在x局部完备所得，则G仍是半无爪图，但G不一定是无爪图.
推论3.7.2若G是半无爪图，则cl(G)是半无爪图.
定理3.7.3若G是半无爪图，则cl(G)是唯一确定的.
在第四章中，我们研究了拟无爪图的最长路，完全圈可扩性以及点可排序泛圈性(vertexpancyclicorderable)，进一步推广了R.J.Faudree，R.J.Gould等人的相应结果.
定理4.1.2连通拟无爪图G有Hamilton路或有长至少为2δ(G)+2的路.
定理4.1.3设G为连通拟无爪图，若δ(G)≥(|G|-2)/3，则G有Hamilton路.
定理4.1.4设G为n阶2-连通拟无爪图，若NC≥(n-2)/2，则G有Hamilton路.
定理4.2.4无孤立点的三角连通的拟无爪图是完全圈可扩的也是点可排序泛圈的(vertexpancyclicorderable).
在第五章中我们定义了一种包含K1，p+1-free图的新的图类-K1,p-扩展图，探讨了它的基本性质，证明了下面的结果：
定理5.2.1无孤立点的三角连通的K1,2-扩展图是完全圈可扩的.