论文部分内容阅读
图的路和圈问题是图论中一个十分重要而且活跃的研究课题,是分析刻画图的有力工具,有大量的实际问题可以归结为图的路和圈问题.图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题.国内外许多学者对此问题作了大量的研究工作.这方面的研究成果和进展可参见文献[38]-[42].其中度条件和邻域并条件成为研究路和圈问题的重要途径,在这方面取得了很多优秀的成果.经过几十年的发展,图的路圈性质所涉及的内容日益丰富和具体.路的方面包括图的Hamilton路(可迹性),齐次可迹性,最长路,Hamilton连通,泛连通,路可扩等等;圈的方面包括图的Hamilton圈,最长圈,(点)泛圈,完全国可扩,点不交的圈,圈覆盖等等. 由于直接研究一般图的Hamilton问题往往比较困难,于是人们转而研究不含有某些禁用子图的图类.继Beinekel970年发表的关于线图性质的文章[17]之后,人们开始关注包含着线图的无爪图.70年代末80年代初,是研究无爪图的一个非常活跃的时期.关于无爪图方面的部分优秀成果可参考[1]-[3],[19]-[31].另外,无爪图的概念也被从不同角度推广到了更大的图类,半无爪图,几乎无爪图,(K1,4;2)-图等.2005年,刘春房在[4]中定义了一种新的图类-[s,t]-图,即任意s个点之间至少含有t条边.程建民在[s,t]-图的基础上提出了强-[s,t]图[51]的概念,即任意s个点之间至少含有t条独立边.[s,t]-图的特点是其边的分布比较均匀,因而在交通网络,通信系统,计算机的网络配置等方面有着很典型的应用. 本文就是研究[s,t]-图的若干路圈性质.