论文部分内容阅读
图的路和圈问题是图论中—个十分重要而且活跃的研究课题,有大量的实际问题可以归结为图的路和圈问题.图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题.国内外许多学者对此问题作了大量的研究工作.这方面的研究成果和进展可参见文献[38]—[42].其中度条件和邻域并条件成为研究路和圈问题的重要途径,在这方面取得了很多优秀的成果.经过几十年的发展,图的路圈性质所涉及的内容日益丰富和具体.路的方面包括图的Hamilton路(可迹性):齐次可迹性,最长路,Hamilton连通,泛连通,路可扩等等;圈的方面包括图的Hamilton圈,最长圈,(点)泛圈,完全圈可扩,点不交的圈,圈覆盖等等.
由于直接研究—般图的Hamilton问题往往比较困难,于是人们转而研究不含有某些禁用子图的图类.继Beineke1970年发表的关于线图性质的文章[17]之后,人们开始关注包含着线图的无爪图.70年代末80年代初,是研究无爪图的一个非常活跃的时期.关于无爪图方面的部分优秀成果可参考[1]—[3],[19]—[31].另外,无爪图的概念也被从不同角度推广到了更大的图类,半无爪图,几乎无爪图,(K1,4;2)—图等.2005年,刘春房在[4]中定义了一种新的图类—[s,t)—图,即任意s个点之间至少含有t条边.而我在这类[s,t]—图的基础上提出了强—[s,t]图,即任意s个点之间至少含有t条独立边,这类图的特点是其边的分布比较均匀,因而在交通网络,通信系统,计算机的网络配置等方面有着很典型的应用.
本文就是研究强—[s,t]图和一般图中与度有关的强路圈性质.
在第一章中,我们主要介绍文章中所涉及的一些概念和术语符号,以及本文的研究背景和已有的一些结果.
在第二章中,我们主要研究了强—[s,t]图在不同条件下的强路圈性质,得到下面的结果:
定理2.1.4设G是n(n≥6)阶强—[4,2]图,则G是泛圈的.
定理2.1.5设G是n(n≥7)阶强—[4,2]图,则G是完全圈可扩的.
定理2.1.6设G是n(n≥8)阶强—[4,2]图,则G是路可扩的,
定理2.2.4设G是n(n≥8)阶连通强—[5,2]图,则C含有Hamilton路.
定理2.2.5设G是δ(G)≥3的连通,局部连通的强—[5,2]图,则G是完全圈可扩的或者同构于图F.
推论2.2.6设G是δ(G)≥3的n(n>8)阶连通,局部连通的强—[5,2]图,则G是完全圈可扩的.
定理2.3.3设G是n(n≥3m-1)阶强—[2m,m]图,则G含有Hamilton路.
定理2.3.4设G是n(n≥3m)阶强—[2m,m]图,则G含有Hamilton圈.
在第三章中,讨论了图中在与度有关的条件下关于圈的几个结果:
定理3.8设G的阶n≥3,如果G中任意一对不相邻的顶点u,v满足d(u)+d(u)≥n+k,则G中任意—个满足n/k+2<|C|<n的圈C是可扩的.
推论3.9设G的阶n≥3,如果G中任意一对不相邻的顶点u,v满足d(u)+d(v)≥3/2n—2,则G是完全圈可扩的,
定理3.10设G的阶n≥3,如果G中任意一对d(u,v)=2的顶点u,v,满足d(u)+d(v)≥n+1,则存在—个顶点x∈{u,v),过x有各种长度的圈.
在第四章中,讨论了图中在与度有关的条件下关于路的几个结果:
定理4.3设G的阶n≥3,如果G中任意一对不同的顶点u,v满足d(u)+d(v)≥n+1,则G是路可扩的.
定理4.4设G的阶n≥3,如果G中任意一对不相邻的顶点u,v满足d(u)+d(v)≥n+1,则C中任意一条满足n/3+1<|P|<n的路P可扩的.