论文部分内容阅读
Hamilton问题是图论研究的基本问题之一,1857年爱尔兰数学家Hamilton提出这样一个问题:“一个连通图是Hamilton图的充要条件是什么?”这个问题至今尚未解决,后来人们发现它是一个NPC问题,于是对它降低要求,间接研究该问题.一种思路是研究Hamilton图的充分条件,另一种思路是研究特殊的图类,如:正则图,t一坚韧图,无爪图,半无爪图等.
关于无爪图的Hamilton性质,近几十年来,许多数学学者致力于它的研究,并且得到了很多优美的结论.Ainouche在文献[2]中首先引进半无爪图的定义,半无爪图是包含无爪图的更大的图类,Ainouche在文献[2]中将无爪图的一些结果,特别是关于Hamilton性质的,推广到半无爪图.本文将无爪图的另外的一些结果推广至半无爪图时也成立.这样,这些性质可以应用到更大的图类上.
本文仅讨论有限、无向、简单图,设G是一个图,V(G)和E(G)分别表示G的顶点集和边集.对任意v∈V(G),N(v)表示点v在G中的邻点集,N[v]=N(v)∪{v}.设G是连通图,对于u,v∈V(G),d(u,v)表示u,v之间的最短路长,称为u,v的距离.若G中无同构与K13的导出子图,则称G是无爪图.如果任意x,y∈V(G),d(x,y)=2,都存在u∈N(x)∩N(y),使得N(u)()N(x)∪N(y),则称G是半无爪图.显然,半无爪图是包含无爪图的更大的图类.
在第一章预备知识中介绍了半无爪图Hamilton性质的研究现状及本文涉及到的图论的一些基本概念、基本知识和使用的有关术语、符号.
关于2-连通无爪图,有以下结果:
定理[3]若G是2-连通的无爪图,其阶为n,则当n≤3δ+2时,G是Hamilton图.
在第二章2-连通半无爪图的Hamilton性质中把这个结果推广至半无爪图:
定理若G是2-连通的半无爪图,其阶为n,则当n≤3δ+2时,G是Hamilton图.
关于3-连通无爪图,有以下结果:
定理[4]若G是3-连通的无爪图,其阶为n,则当n≤5δ-5时,G是Hamilton图.
在第三章3-连通半无爪图的Hamilton性质中将这个结果推广至半无爪图类,并且把n的值提高到5δ-4,证明了半无爪图的以下结果:
定理若G是3-连通的半无爪图,其阶为n,则当n≤5δ-4时,G是Hamilton图.
关于k-连通半无爪图有以下结果:
定理乜]若G是k-连通的半无爪图(k≥2),如果对于G中任意基数为k+1的独立集X,都有∑v∈Xd(v)≥n-k,则G是Hamilton图.
在第四章k-连通半无爪图的Hamilton性质中证明以下结论,它减弱了以上定理的条件:
定理若G是k-连通的半无爪图(k≥2),如果对于G2中任意基数为k+1的独立集X,都有∑v∈Xd(v)≥n-k,则G是Hamilton图.
在第五章图的控制圈的一个下界中得到以下结论,它在特定的条件下推广了田丰在[19]中的结果:
定理若G是2-连通的非Hamilton图,含有一个控制圈C,令R:V(G)-V(C),如果存在v∈V(C),使dR(v)≥2,则G包含的控制圈的长至少为2σ-2.