论文部分内容阅读
路、圈问题是图的两种基本结构,是分析、刻画图整体结构的有力工具.从而,图的路、圈问题是图论中非常活跃而且重要的研究课题,实际中的大量问题可以归结为图的路、圈问题.对图的路、圈性质的研究是在Hamilton问题(图论中三大难题之一)的基础上发展而来的. 对于这方面的问题,国内外许多学者做了大量的研究工作,并且取得了不少成果和进展,可参见文献[38]-[42].对图的路、圈性质的研究一直是图论中的热门领域,至今为止,图的路、圈性质所涉及的内容日益丰富和具体.路的方面包括图的Hamilton路(可迹性),齐次可迹性,最长路,Hamilton连通,泛连通,路可扩等等;圈的方面包括图的Hamilton圈,最长圈,(点)泛圈,完全圈可扩,点不交的圈,圈覆盖等等. 由于直接研究一般图的Hamilton问题往往比较困难,于是人们转而研究一些特殊图的Hamilton问题,比如在不含有某些禁用子图的图类上作研究。其中有代表性的是无爪图,它是以K1,3为禁用子图的图类,研究该图类的最初动机来源于Beinekel970年发表的关于线图性质的文章[18].70年代末80年代初,对无爪图的研究成为图论中的著名课题,关于无爪图方面的优秀成果和综述性的文章可参考[1]-[3],[19]-[35].在此基础上,无爪图的概念也被从不同角度推广至半无爪图,几乎无爪图,爪心独立图,(K1,p;q)-图等.近年来其它一些新型的禁用子图不断被提出. 2005年,刘春房在[5]中定义了一种新的图类[s,t]图,即任意s个点之间至少含有t条边.程建民在[s,t]-图的基础上提出了强[s,t]图[52]的概念,即任意s个点之间至少含有t条独立边.提出这两类图的目的是想让图中的边分布比较均匀,能更多、更好的研究图的性质,而且在交通网络,通信系统,计算机的网络配置等方面有着很典型的应用. 本文就是研究[s,t]-图的路和圈性质. 在第一章中,我们主要对文章中所涉及的概念和术语符号进行介绍,以及本文的研究背景和已有的一些结果.