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