| 【论文摘要】 | 在这篇论文中,我们只考虑阶数为n的有限,无向简单图G=(V,E)。
一个图G的一个Hamilton圈(或路)是指包含G的每一个顶点的圈(或路)。一个图G称为Hamilton图(或可迹的),如果它包含一个Hamilton圈(或路)。在图G中最长圈的长度被称为G的周长,并且用c(G)来表示。因此如果c(G)=n,则G是Hamilton图。图G称为是Hamilton连通的,如果对于V中的每一对不同的顶点(a,b),在G中都存在一条以a和b为端点的Hamilton路。
本文由3章组成。在第一章介绍了基本概念和术语之后,在第二章中,我们讨论了连通图中一类圈和路的存在性。一个图H称为图G的一个minor,如果H可以通过收缩G的一个子图的边而得到。显然一个图的每一个子图也是它本身的minor。众所周知,minor定理指出每一个包含无穷多个图的集合中一定存在两个图,其中一个是另一个的minor。Dcan猜想一个k-连通(k≥2)非Hamilton图总存在一个圈包含k个独立点和它们的邻点。他还猜想一个k-连通(k≥1)非可迹的图G存在一条路包含k+1个独立点和它们的邻点。正如Dean在[5]中所提到的,k=2,3时... |
