论文部分内容阅读
路和圈是图的两种基本结构，是分析和刻画图的有力工具，有大量的实际问题可以归结为图的路和圈问题，所以这方面一直是图论中的热点研究领域．关于路和圈的进展，已经取得了长足的发展，这方面的研究成果和进展可参见文献[12]—[14]．事实上，图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题．经过几十年的发展，图的路圈性质所涉及的内容日益丰富和具体．路的方面包括图的Hamilton—路(可迹性)，最长路，Hamilton连通，泛连通，路可扩等等；圈的方面包括图的Hamilton圈，最长圈，(点)泛圈，完全圈可扩，点不交的圈，圈覆盖等等。
由于直接研究一般图的Hamilton问题往往比较困难，于是人们转而研究不含有某些禁用子图的图类，继Beineke1968，1970年发表的关于线图性质的两篇文章之后，人们开始关注包含着线图的无爪图．70年代末80年代初，是研究无爪图的一个非常活跃的时期．关于无爪图方面的部分优秀成果可参考[1]—[3]，[17]—[22]．[23]是关于无爪图的综述性的文章．另外，无爪图的概念也被从不同角度推广到了更大的图类，如半无爪图，几乎无爪图，(K1，4；2)—图，DCT图等．1994年，Z．Ryjacek定义了一种包含无爪图的更大的图类—几乎无爪图．之后，亦出现了不少研究这类图的Hamilton问题的学术论文，如[28]—[30]．但事实上，无爪图中很多很好的结果推广到几乎无爪图难度非常大．所以，滕延燕，尤海燕2003年[4]在此基础上提出了拟无爪图的概念，它包含无爪图类但却包含在几乎无爪图类中．这里，我们可以将半无爪图，几乎无爪图，拟无爪图统称为类无爪图。
2006年，曲晓英提出了K1，p—扩展图的概念．我们在研究不同图类结构的基础上对K1，p—扩展图的概念作了进一步的完善．{x1，x2，…，xp)∈V(G)(p≥2)是图G中任意独立集，若存在u∈N(x1)∩N(x2)∩．．．∩N(Xp)，使得N[u]∈()N[x1]∪N[x2]∪…∪N[xp]，则称u为．[x1，x2，…，xp)的扩展点，若存在v∈N(u)，v()N[x1]∪N[x2]∪…∪N[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)．{x1，x2，…，xp)∈V(G)(p≥2)是图G中任意独立集，如果满足D(x1，x2，…，xp)≠φ，且()u∈D(x1，x2，…，xp)，()v∈—D(x1，X2，…，xp)，有uv∈E(G)，则称G为K1，p—扩展图．特别的，K1，2—扩展图是包含着无爪图类且比无爪图类更大的图类．我们深入的研究了K1，p—扩展图的Hamiltorn性质及路可扩性。
对()v∈V(G)，若G[N(v)]是连通的，则称v是G的一个局部连通的点．若G的任一点都是局部连通的点，则称G是局部连通的．在局部连通的定义提出之后，张存全在1989年提出了半局部连通的定义，研究了无爪图在半局部连通条件下的一些性质．滕延燕和尤海燕在2002年定义了几乎局部连通．而赖宏建在2004年提出了三角连通的概念，证明了无爪图在三角连通下的一些结果．2008年，刘明颖提出了H—局部连通的概念，初步讨论了H—局部连通下的无爪图和半无爪图的路圈性质．我们在此基础上，讨论了H—局部连通下拟无爪图的一些性质，对H—局部连通下类无爪图的性质进行了很好的完善。
本文主要研究了K1，p—扩展图和拟无爪图在不同条件下的路圈性质。
在第一章中，我们主要介绍了本文的研究背景以及已有的一些结果，以及文章中所涉及的一些概念和术语符号。
在第二章中，我们具体讨论了K1，p—扩展图的Hamilton性质及路可扩性，得到下面两个结果：
定理2.1.4连通的K1，2—扩展图若满足()x，y∈V(G)，—D(x，y)≠φ，则G有Hamilton路。
定理2.2.7 G是连通，局部2—连通的K1.2—扩展图，P是G的一条非Hamilton，路，()u，u∈Vp(x)(x∈V(G)—V(P))，若当u，v分别是x与其各自前点(或后点)的扩展点时，有u—v+，u+v—∈E(G)，则G是路可扩的。
在第三章中，我们通过具体实例讨论了在不同局部连通条件下的拟无爪图及拟无爪图的圈可扩性，证明了下面的结果：
定理3.1.3三角连通的拟无爪图是半局部连通的。
推论半局部连通的拟无爪图的最小点割的阶数至少是2。
定理3.2.4连通，半局部连通，无网全爪的拟无爪图是完全圈可扩的且无网全爪条件是必须的。
在第四章中，我们探讨了H—局部连通的拟无爪图的性质，Hamilton性质及圈可扩性，得到如下结果：
定理4.1.2阶≥2m(m≥2)的连通，Km—局部连通拟无爪图是2—连通。
定理4.1.4 G是K2—局部连通拟无爪图，()xy∈E(G)，则G[N(xy)]中任意两点间的最短路不超过6。
定理4.1.6设G是K3—局部连通拟无爪图，G[{x，y，zH是G的任意三角形，则G[N(xyz)]中任意两点的最短路的长不超过8。
定理4.2.2设G是阶不小于4的连通，K2—局部连通拟无爪图，则G是Hamilton的。
定理4.3.2设G是δ≥3的连通，K2—局部连通拟无爪图，则G是完全圈可扩的。