连通图中一类圈和路的存在性

论文摘要

在这篇论文中,我们只考虑阶数为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时第一个猜想已经被证明了（参看[7]和[14]）。当k=2时Dean的两个猜想可以从Dirac[6]所给的一个证明中得到（可参看[13]中的练习10.27）;另外,第二个猜想的k=1,2的情况是容易的。通过研究一个k-连通非Hamilton图（或非可迹的）的一个最长圈C上的两个相继顶点在圈C外有邻点的情形,我们证明了当n≤3δ时,Dean的两个猜想是对的,这里δ是G的最小度。在第三章,我们给出了关于3-连通图的最长圈的一个注。一个图是否为Hamilton图的问题很难回答。直到现在,也不知道关于一个图是Hamilton图的容易验证的充分必要条件。而且,对于如何确定一个给定的图是否包含一个给定长度的圈,或包含一个长度超过某个最小值的圈的问题都没有满意的回答。由此,导致了大量的各类圈存在的必要或充分条件的出现。Dirac[6]的一个著名的结果是,如果G是2-连

论文目录

• Abstract
• 1.1 Introduction
• 1.1 Terminology and preliminaries
• 1.2 Some known results
• 1.2 Existence of a kind of cycles and paths in connected Graphs
• 2.1 Introduction and main results
• 2.2 The proof of Theorem 2.1.1
• 1.3 A Note on the circumference of 3-connected Graphs
• 3.1 The main results
• 3.2 The proof of Theorem 3.1.1
• Bibliography
• Acknowledgement