论文部分内容阅读
圈和路是图的两种基本结构.是分析和刻画图的有力工具.大量的实际问题都可以归结为图的圈和路问题.对图的圈路性质的研究是在图论中的著名问题-Hamilton问题的基础上发展来的.而关于图的哈密顿性的研究.已经取得了长足的发展.这方面的研究成果和进展可参见文献[26]-[29].图的圈路性质一直是图论中的热门研究领域.经过几十年的发展.圈路性质所涉及的内容日益丰富和具体.圈的方面包括图的Hamilton圈.最长圈.(点)泛圈.完全圈可扩.点不交的圈.圈覆盖等等:路的方面包括图的Hamilton路(可迹性).最长路.Hamilton连通.泛连通.路可扩等等.另外.在图连通性方面.一些学者不断提出新的概念.比如N2-局部连通.三角连通.四角连通等.为图的圈路性质的研究提供了新的思路.
由于直接研究一般图的圈路性质往往比较困难.所以若干年来相关的研究主要集中在一些特殊匿类上.即不含有某些禁用子图的图类.其中比较有代表性的是无爪图.它是以K1.3为禁用子图的图类.继Bcinckcl968.1970年发表的关于线图性质的两篇文章[30]-[31]之后.人们就开始关注包这种含着线图的无爪图.70年代末80年代初.是研究无爪图的一个非常活跃的时期.至今在这方面已取得了相当多的研究成果.另外.无爪图的概念也被从不同角度推广到了更大的图类.如爪心独立图.半无爪图.几乎无爪图.(K1.p:q)-图.拟无爪图等.近年来.一些新型图类不断被提出.P3-控制图就是其中一种.这种图类包含半无爪图是半无爪图的推广.2006年.南开大学的两位访问学者H.J.Broersma和E.Vumar首次提出了P3-控制图的概念.并得出一系列成果.参见文献[2].本文主要对P3-控制图进行了初步探索.得出其圈路方面的几个结果.另外还讨论了(K1.4:2)-图的点泛圈性.