论文部分内容阅读
路和圈是图的两种基本结构，是分析和刻画图的有力工具，有大量的实际问题可以归结为图的路和圈问题，所以这方面—直是图论中的热点研究领域。关于路和圈的进展，已经取得长足的发展，这方面的研究成果和进展可见参考文献。事实上，图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题，经过几十年的发展，图的路圈性质所涉及的内容日益丰富和具体，包括：Hamilton路、Hamilton圈、最长路、最长圈、Hamilton连通、泛连通、(点)泛圈、路可扩、圈可扩等。
1952年和1960年，Dirac和Ore分别用顶点的度作为条件研究路和圈问题，得到著名的Dirac定理和Ore定理．1989年，朱永津提出图中顶点隐度的概念．1987年，Faudree，Gould，Jacobson，Schelp创立了Neighborhood unions conditions，从邻域的角度给出路和圈问题的充分条件．第一章，主要介绍本文的研究背景、已有的结果及文中所涉及的一些概念和术语符号。第三、四章，将继续从邻域和隐度的角度来探索路和圈问题的充分条件。2006年，刘晓妍提出了s—点连通图的概念。
1.提出一般性的概念：(s，k)—连通图的概念，进而得到下面结果：定理2.2.1 G是n阶(s，k)—连通图，若s—k≤n-1/2，则G是路可扩的．推论2.2.2 G是n阶图，若K(G)≥n+1/2，则G是路可扩的。
2.讨论邻域条件下图的路、圈，得到结果：定理3.1.1 G是2—连通图，若()v∈V(G)，G[N2(v)]是完全图，则G是泛圈的．定理3.1.2 G是2—连通图，若()v∈V(G)，G[N2(v)]是完全图，则G是可迹的。定理3.2.1 G是2—连通图，若G中导出K1，3或K1，3+e中的不相邻两点u，v均有[N(u)UN(v)|≥m(m，是正数)，则G有Hamilton圈或者有长至少为m+2的圈．定理3.2.2 G是2—连通n阶图，若G中导出K1，3或K1，3+e中的不相邻两点u，v均有|N(u) UN(v)|≥n—δ，则G是Hamilton图。
3.讨论了在隐度条件下Hamilton圈，推广了顾国华，卫兵，余荣祖等人的结果：定理4.1.2 G是2—连通n阶图，若G中满足|N(u)∩(Nv)|≤a(G)-1的不相邻两点u，v均有d1(u)+d1(v)≥n/2+δ(G)，则G是Hamilton图．定理4.1.5 G是2—连通n阶半无爪图，a，b是G中满足d2(a)+d2(b)≥n不相邻两点，则G是Hamilton图当且仅当G+ab是Hamilton图。定理4.2.2 G是2—连通图，若对于G中任意独立集S={u，c，w}，存在x，y∈S(x≠y)使得如d2(x)+d2(y)≥c(c是正数)，则G有Hamilton圈或者有长至少为c的圈。