图的度与路可扩性

论文摘要

路和圈是图的两种基本结构,是分析和刻画图的有利工具。有大量的实际问题可以归结为图的路和圈问题。所以图的路和圈问题是图论中一个十分重要而且活跃的研究课题。图论中三大著名难题之一的Hamilton问题,本质上也是图的路和圈问题。关于图的路和圈问题,国内外许多学者对此问题作了大量的研究工作。这方面的研究成果和进展可参见文献[2]-[12]。其中图的顶点的度性条件（包括顶点的最小度、任意两点的度和等）成为研究路和圈问题的重要途径,在这方面取得了很多优秀的成果。经过几十年的发展,图的路圈性质所涉及的内容日益丰富和具体。路的方面包括图的Hamilton路,最长路,Hamilton连通,泛连通,路可扩等等；圈的方面包括图的Hamilton圈,最长圈,（点）泛圈,完全圈可扩等等。本文主要对图的度性条件（包括顶点的最小度、任意两点的度和等）与图的路圈性质（包括路可扩、完全圈可扩等）之间的关系进行了一些探索,得出了路可扩的几个充分条件。在第一章中,主要介绍了本文的研究背景和已有的一些结果,以及文章中所涉及的一些概念和术语符号。在第二章中,主要研究了图的最小度以及任意两点的度和与路可扩、圈可扩之间的关系,得到下面的结果：定理2.5设G是n阶图,如果G中任意一对不同的顶点u,v满足d（u）+d（v）≥n+2,则G是路可扩的。在第三章中,我们在第二章的基础上,继续探求图路可扩的充分条件,得到下面的几个结果：定理3.6设G是n阶图,如果σ2（G）≥n+k（k是正整数）,则G中任意一个满足n/（k+2） +2≤|P|<n的路P是可扩的.这里路长的下界n/（k+2） +2是最好可能的.推论3.7设G是n阶图,如果σ2（G）≥3/2n-1,则G是路可扩的.

论文目录

• 中文摘要
• 英文摘要
• 第一章 预备知识
• 1.1 研究背景
• 1.2 符号概念介绍
• 1.3 已有结果
• 第二章 图的最小度与路可扩性
• 第三章 图的度和与路可扩性
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢