论文部分内容阅读
在图论中,我们研究的一个十分重要而且非常活跃的课题为图的路和圈的问题,而实际生活中的很多问题都可以归结为图的路和圈问题.图论中的Hamilton问题本质上也是图的路和圈问题,它是图论中的三大著名疑难问题之一.国内外许多学者在这一方面作了大量的研究工作.这方面的研究成果和进展可参见文献[31]-[35].其中度条件、邻域和条件以及邻域并条件成为研究路和圈问题的重要途径,在这方面取得了很多优秀的成果.经过几十年的研究和发展,图的路圈性质所涉及的内容日益丰富和具体.其中路方面包括图的Hamilton路(可迹性),齐次可迹性,最长路,Hamilton连通,泛连通,路可扩等等;圈的方面包括图的Hamilton圈,Dominating圈,最长圈,(点)泛圈,完全圈可扩,点不交的圈,圈覆盖等等.由于图的Hamilton问题是一个疑难问题,所以在一般图中研究Hamilton问题会更加困难,于是人们转而研究不含有某些禁用子图的图类,如无爪图.继Beineke1970年发表的关于线图性质的文章[29]-[30]之后,人们开始关注包含着线图的无爪图.70年代末80年代初,是研究无爪图的一个非常活跃的时期.关于无爪图方面的部分优秀成果可参考[13]-[28]另外,无爪图的概念也被从不同角度推广到了更大的图类,如半无爪图,几乎无爪图等.本文主要对图的度条件(任意两个不相邻子图的度和)与路圈性质(包括Hamilton连通,可迹性及Hamilron圈等)之间的关系进行了一些探索,得出了一般图及无爪图的路圈性质的几个充分条件.在第一章中,我们主要介绍文章中所涉及的一些概念和术语符号,以及本文的研究背景和已有的一些结果.在第二章中,我们主要研究了一般图及无爪图在不同度条件下的路圈性质,得到下面的结果:定理2.1.3设G是n阶2-连通图,如果G中任意两个同构于K2(2阶完全图)的不相邻子图H1,H2的度和d(H1)+d(H2)≥n—2,则G有Dominating圈.推论2.1.4设G是n阶2-连通图,如果对G中任意一个同构于K2的子图H,有d(H)≥n-2/2,则G有Dominating圈.定理2.2.4设G是n阶2-连通无爪图,如果G中任意两个分别同构于P3与K2(2阶完全图)的不相邻子图H1,H2满足d(H1)+d(H2)≥n—2,则G有Hamilton圈.定理2.3.1设G是n阶3-连通无爪图,如果G中任意两个分别同构于K3(3阶完全图)与K1的不相邻子图H1,H2满足d(H1)+(d(H2)≥n—3,则G有Hamilton圈.在第三章中,讨论了无爪图在度条件下的Hamilton连通性质,得到下面的结果:定理3.5设G是n阶3-连通无爪图,如果G中任意两个分别同构于P3与K1的不相邻子图H1,H2满足d(H1)+d(H2)≥n,则G是Hamilton连通的.在第四章中,讨论了半无爪图在度条件下的可迹性,得到下面的结果:定理4.4设图G是n阶2-连通半无爪图,如果G中任意两个同构于K3和K1的不相邻导出子图H1,H2的度之和d(H1)+d(H2)≥n—1,则G是可迹的.