论文部分内容阅读
该文仅讨论有限、无向、简单图,设G=(V(G),E(G))是一个图,其中V(G),E(G)分别表示图G的顶点集和边集.设G=(V(G),E(G))是一个图,S V(G).由S导出的子图记为.若E(S)=φ则称S为G的一个独立集,G的最大独立集的顶点数记为α.δ(G)表示G的顶点的最小度.如果对u∈V(G)S,x∈S,使ux∈E(G),则称S为G的一个控制集,S中的点叫控制点.当控制集S={v}时,v称为G的全控点.G的最小控制集(所含顶点的个数达到最小的控制集)中顶点的数目用γ(G)表示.当γ(G)≤k时,G称为k-控制的.记D(G)={v∈V(G):不连通},若D(G)是独立集,而且 v∈D(G),局部连通u,使连通,则称G是弱局部连通的;若D(G)是独立集,而且 v∈D(G), u,使连通,则称G是几乎局部连通的.当D(G)=φ时,G称为局部连通.Hamilton问题是图论研究的基本问题之一,主要集中在以下两个方面:圈问题及路问题,具体地讲主要有:Hamilton圈问题、圈可扩问题,最长圈问题等以及Hamilton路问题,Hamilton连通问题,泛连通问题,路可扩性问题,最长路问题等,关于Hamilton圈的问题,已经取得了长足的发展,1952年Dirac给出了图中圈存在的最小度条件(称为Dirac条件),1960年ore给出了度和条件(称为ore条件),在很多条件下ore条件减弱了Dirac条件,得到了更好的论证,1984年,范更华在[9]中给出了距离为2的点对中较大度条件(称为Fan条件),由于直接研究任一图类的Hamilton问题往往比较困难,于是人们转而研究特殊图类如无爪图、几乎无爪图、拟无爪图、距离无爪图以及K<,1,P>约束图等的Hamilton问题.关于无爪图的路问题有如下一些结论:定理<[2]>连通,局部2-连通的无爪图是路可扩的定理<[6]>设G为连通的无爪图,则G有Hamilton路或长至少为2δ+2的路.定理<[6]>设G为连通的无爪图,|G|=n,δ≥n-2/3,则G有Hamilton路.关于特殊图类的Hamilton圈问题也有一些结论,该文对以下结果感兴趣:定理A<[10]>顶点数不小于3的连通,局部连通的无爪图是哈密顿图.后来许多图论专家发现该定理的条件隐含着更强的圈性质,其中Hendry证明下面定理.定理B<[3][11]>顶点数不小于3的连通,局部连通的无爪图是完全圈可扩的.朱永津、王江鲁证明了下面的定理定理C<[29]>顶点数不小于3的连通,局部连通的K<1,P>-约束图是完全圈可扩的.定理D<[30]>连通,几乎局部连通的拟无爪图是完全圈可扩的.受上述定理的启发,该文在弱局部连通以及几乎局部连通的条件下,分别讨论了K<,1,P>约束图及强K<,1,P>约束图的完全圈可扩性,它们分别推广了定理C及定理D的结论.另外,距离无爪图类作为特殊无爪图类,该文感兴趣的结果有:定理E<[31]> G∈DC,G是2-连通的,则G有Hamilton路.定理F<[31]> G∈DC,且G是3-连通的,则G有Hamilton图.我们在定理E、F的理论基础上,研究了距离无爪图在2-连通条件下的Hamilton圈问题.第一章中,我们主要介绍该论文所涉及的一些基本概念和符号.第二章中,我们给出了弱局部连通的定义,并在此条件下研究了K<,1,P>-约束图的完全圈可扩,另外,在几乎局部连通的条件下,研究了强K<,1,P>-约束图的完全圈可扩,得到以下引理及定理:引理1<[32]>对于K<,1,P>-约束图而言,若图C中存在局部连通点与圈外点相邻,则圈C有1-扩张.定理2.2<[32]>顶点数≥3的连通,弱局部连通的K<,1,P>-约束图是完全圈可扩的.定理2.3<[33]>顶点数≥3的连通,几乎局部连通,强K<,1,P>-约束图是完全圈可扩的.在第三章中,提出另一个新禁用子图--网全爪图,该概念的提出是该章的创新点,得到如下定理:定理3.1<[34]>2-连通的无网的距离无爪图有Hamilton圈.定理3.2<[34]> 2-连通的无网全爪的距离无爪图有Hamilton圈.