论文部分内容阅读
在图论中,路和圈是图的两种基本结构,是分析和刻画图的常用工具,而且在实际生活中,有很多实际问题可以归结为图的路和圈问题,所以这一问题一直是图论中重要的热点问题.图论中的Hamilton问题本质上也是图的路和圈问题,它和四色问题还有并称图论的三大著名难题.国内外诸多学者在这方面做了大量的研究工作,其研究成果和进展可参见文献[29]一[37].经过几十年的研究和发展,图的路圈性质所涉及的内容日益丰富和具体.其中路方面包括图的Hamilton路(可迹性),齐次可迹性,最长路,Hamilton连通,泛连通,路可扩等等;圈的方面包括Hamilton,Dominating圈,最长圈,(点)泛圈,完全圈可扩,点不交的圈,圈覆盖等等. 然而直接研究一般圈的Hamilton问题往往比较困难,所以人们常常转而研究某些特殊图类,例如不含某些禁用子图的图类.其中度型条件、邻域和条件以及邻域并条件成为研究路和圈问题的重要途径.继1970年Beineke发表的关于线图性质的文章[27]一[28]之后,人们开始关注包含着线图的无爪图.70年代末80年代初,对于无爪图的的研究进入了一个活跃时期,关于无爪图方面的部分优秀成果可参考文献[11]-[26].另外,无爪图的概念也被从不同角度推广到了更大的图类,如半无爪图,几乎无爪图等. 本文主要对图的度型条件(即任意两个不相邻子图的度和)与路圈性质(包括Hamilton连通,可迹性及Hamilton圈等)之间的关系进行了一些探索研究,得出无爪图以及半无爪图的路圈性质的几个充分条件. 在第一章中,我们主要介绍文章中所涉及的一些概念和术语符号,以及本文的研究背景和已有的一些结果. 在第二章中,我们主要研究了无爪图及半无爪图在不同度型条件下的路圈性质,得到下面的结果(公式略). 在第三章中,讨论了无爪图在不同度型条件下的Hamilton连通性质,得到下面的结果(公式略). 在第四章中,讨论了无爪图在度条件下的可迹性,得到下面的结果(公式略).