论文部分内容阅读
图的哈密顿问题是图论中一个十分重要且又十分活跃的研究课题,每年都有大量的关于这一问题的学术论文。1857年,爱尔兰数学家哈密顿提出:“一个连通图有哈密顿圈的充要条件是什么?”这样一个问题。但是这个问题至今仍未能解决。后来人们发现它是一个NPC问题,于是降低要求间接研究该问题。与此同时,以Hamilton问题为出发点发展起了对图的圈性质的研究,这些性质主要包括Hamilton性、泛圈性、完全圈可扩性等。我们知道图的完全圈可扩性要比图的泛圈性更强,图的泛圈性要比图的哈密顿性更强,所以研究泛圈性和完全圈可扩性就研究了图的Hamilton性。关于哈密顿性的研究及最新进展可见参考文献[17]-[23]。关于泛圈性的研究及最新进展可见参考文献[24]-[34],关于完全圈可扩性的研究及最新进展可见参考文献[4]-[15]。对这些性质的研究主要集中在两方面,一方面是寻求这些圈性质的充分条件,另一方面是研究某些特殊图类的圈性质。
本文主要讨论了两种特殊图类中的圈性质的问题。一种图类是[s,t]-图,刘春房最早提出了[s,t]-图的概念并进行研究的。对[s,t]-图的研究有着深刻的应用价值,很典型的一个应用就是在计算机的网络配置上。另一种图类是高连通度图。这里的高连通度是指一个图的连通度相对图的阶是较高的。当一个图的连通度足够高时,这个图可以保证图的各种圈性质,那么随着图的连通度的降低,图的圈性质将发生什么变化呢?本文就此讨论了高连通度图的完全圈可扩性。为方便讨论,在第三章中提出了s-点连通图的概念,即连通度为κ(G)=|G|-s+1的图。在此基础上主要讨论了5-点连通图,6-点连通图的完全圈可扩性,即连通度分别为|G|-4和|G|-5的高连通度图的完全圈可扩性。根据所得结果提出了s-点连通图(κ(G)=|G|-s+1)在完全圈可扩性方面的一个猜想。在第三章最后给出例子说明定理及猜想中对图G的阶的限制是最好可能的。
本文的主要内容包括三章。在第一章中,我们主要介绍了文章中所涉及的一些概念、术语符号和本文的研究背景及已有的结果;在第二章中,我们讨论了2-连通[4,2]-图中的圈;在第三章中,我们讨论了高连通度图的完全圈可扩性并提出猜想。
我们得到的主要结果如下:定理2.1.1设G是2-连通[4,2]-图,C是G中满足|V(C)|<|V(G)|的任一圈,则或者G中有(|C|+1)-圈,或者G同构于K2,3,K1,1,3,F1,F2,F3,F4,F5。(其中F1,F2,F3,F4,F5如下图)推论3.1.1设G为4-点连通图且|G|≥7,则G是完全圈可扩的。定理3.1.1设G为5-点连通图且|G|≥9,则G是完全圈可扩的。定理3.1.1′设G满足κ(G)=|G|-4且|G|≥9,则G是完全圈可扩的定理3.1.2设G为6-点连通图且|G|≥11,则G是完全圈可扩的。定理3.1.2′设G满足κ(G)=|G|-5且|G|≥11,则G是完全圈可扩的。由上述定理提出下面的猜想猜想3.1.1设G为s-点连通图且|G|≥2s-1,则G是完全圈可扩的。
猜想3.1.1′设G满足κ(G)=|G|-s+1且|G|≥2s-1,则G是完全圈可扩的。
猜想3.1.1″设G为s-点连通图,若s≤[|G|+1/2],则G是完全圈可扩的。
猜想3.1.1"设图G满足κ(G)≥[|G+|+1/2],则G是完全圈可扩的。