论文摘要
路和圈是图的两个基本结构，是分析、刻画图的整体结构的有力工具。大量的实际问题都可以归结为图的路圈问题。图论问题中三大著名难题之一hamilton问题本质上也是图的路和圈的问题，对图的路和圈的问题的研究一直是图论研究中的热点领域。最近若干年来，关于这方面的研究主要集中在路圈问题，具体的讲主要集中在：hamilton圈，泛圈，点泛圈，圈可扩，最长圈，hamilton连通，泛连通，hamilton路，路可扩，最长路等性质的研究上，而且取得了长足的发展。关于这方面的研究及最新研究参看[2]-[16]。对这些性质的研究主要集中在两个方面：一方面是寻求图的路圈性质的充分条件；另一方面是研究某些特殊图类的路圈性质。连通度是图论中较早提出的一个概念，是刻画图的“连通程度”的一个重要指标。可以想象，当一个图的连通度相对图的阶是较高时，可以保证图的各种性质路圈性质，随着连通度逐渐降低，图的各种性质路圈性质也将发生变化乃至消失。连通度应满足什么条件才能保证图的路圈性质呢?因此能够保证图具有某种路圈性质的连通度的下确界是什么自然就是一个很值得关注和研究的问题，但是在图的路圈性质的研究中，目前这方面的研究还不多。为了寻图的完全圈可扩性与连通度的下确界的关系，2006年刘晓妍研究了连通度为|G|-3，|G|-4，|G|-5的图G的完全圈可扩性，得到了以下结果：定理1设G满足κ（G）=n-3且|G|≥7，则G是完全圈可扩的。定理2设G满足κ（G）=n-4且|G|≥9，则G是完全圈可扩的。定理3设G满足κ（G）=n-5且|G|≥11，则G是完全圈可扩的。根据以上三个结果反映出来的规律，刘晓妍提出如下猜想：猜想1若G满足κ（G）=|G|-s+1且|G|≥2s-1，则G是完全圈可扩的。并且说明了如果猜想1成立，则其中的连通度的下界是最好可能的，并进一步得到了定理5。定理5若G满足κ（G）≥（|G|+1）／2，则G是完全圈可扩的。本文延续了刘晓妍思路，做了两方面的工作。首先证明了刘晓妍提出的猜想，（不妨把猜想1称为定理4），定理5。定理4若G满足κ（G）=|G|-s+1且|G|≥2s-1，则G是完全圈可扩的。定理4，定理5揭示了图的完全圈可扩与连通度之间的联系规律。另一方面，为了寻求路可扩性与连通度之间的关系，本文仿照刘晓妍的思路，研究了连通度为|G|-3，|G|-4，|G|-5的图的路可扩性，即定理6若G满足κ（G）=|G|-3且|G|≥7，则G是路可扩的。定理7若G满足κ（G）=|G|-4且|G|≥9，则G是路可扩的。定理8若G满足κ（G）=|G|-5且|G|≥11，则G是路可扩的。根据以上三个结果反映出来的规律，提出猜想：猜想2若G满足小κ（G）=|G|-s+1且|G|≥2s-1，则G是路可扩的。仿照定理5，得到猜想3。猜想3若G满足κ（G）≥（|G|+1）／2，则G是路可扩的。此猜想显然包含了定理4，并且说明了如果猜想成立，那么其中连通度下界是最好可能的。遗憾的是在尝试了对猜想2，猜想3证明的过程中，在一些特定的情况下遇到了一定的困难，由于时间的原因，在本文完成之前，证明还未完全做出。本文分为两章。在第一章中，主要介绍了论文中所涉及到的一些概念、术语、符号、本文的研究背景及已有的研究结果。在第二章中，研究了连通度与完全圈可扩、路可扩之间的联系，主要证明了引理2，引理3，定理4，定理5，定理6，定理7，定理8。