论文部分内容阅读
如果一个图中含有Hamilton圈,即经过图中所有顶点的圈,那么这个图被称为是Hamilton的.本论文研究了图的Hamilton性的一类充分条件——重子图条件,推广了 Bedrossian和Faudree等人关于图的Hamilton性的禁止子图条件的结论.本论文的研究基于如下的问题:我们已知在图中禁止了某些子图结构时,能够保证所给的图是Hamilton的.如果我们允许这些子图结构存在,那么在这种子图结构上限制什么样的条件,能够仍然保证所给的图含有Hamilton圈?设G是一个图.对于给定的图H,如果G不含同构于H导出子图,那么我们说G是无H的(或H是G的禁止子图).1991年Bedrossian在其博士论文中刻画了这样的连通图对{R,S}:使得任何2-连通无R无S图是Hamilton的.设P是关于G的导出子图的某种性质.如果G中每个同构于H的导出子图G"都满足P,那么我们说G满足P(H).显然,如果G是无H的,那么G自然满足P(H).本论文研究的主要问题是:对于什么样的子图R和什么样的子图性质P,一个图G满足P(R)可以保证G是Hamilton的.我们称这种类型的充分条件为重子图条件.因此重子图条件有两个要素,即子图R和附加于子图的限制条件P.本论文对于所考虑的几类限制条件,完整刻画了能够保证任意2-连通图是Hamilton的所有子图.这些结论推广了 Bedrossian等人关于禁止子图条件的结果.此外,本文还讨论了有关图的Hamilton性的一些相关性质,包括图的最长圈经过大度顶点的性质和图中2-因子的存在性.在第一章,我们介绍了一些基本概念和本文所研究的问题的背景,并且列出了本论文得到的结论.从第二章到第六章,我们给出了某些类型的重子图条件.我们研究了所给条件下能够保证图的Hamilton性的子图.对于给定的图H,我们称图G是H-o-重的,如果图G的每一个同构于H的导出子图都含有两个不相邻的顶点度和至少为n(n是图G的阶).为研究无爪图和爪-o-重图的Hamilton性,Ryjacek和Cada分别提出了无爪图的闭包理论和爪-o-重图的闭包理论.在第二章我们介绍了闭包理论,这是本论文的一个重要工具.Ryjacek在2002年刻画了无爪图的闭包的结构.基于Ryjacek的刻画,我们刻画了爪-o-重图的闭包的结构.第三章考虑了无爪图的子图端点度条件.对于给定的图H,如果图G的每一个同构于H的子图的每个端点的度至少为(n+ k)3,那么我们称G满足Φ(H,k).Broersma在1993年提出一个猜想:任意2-连通无爪图若满足Φ(N,-2)则是Hamilton的.在第三章,我们刻画了所有这样的连通图R:使得任意2-连通无爪图若满足Φ(R,3)则是Hamilton的.我们的结论部分证明了Broersma的猜想.第四章考虑了爪-o-重图的c-重子图条件.对于给定的图H,如果G的每一个同构于H的导出子图G′和G″的每个极大团G″-C的每个非平凡分支都有一个顶点的度至少为n/2,那么我们称G是H-c-重的.我们完整刻画了使得任意2-连通爪-o-重R-c-重图是Hamilton的所有连通图R.第五章考虑了爪-o-重图的p-重子图条件.对于给定的连通图H,如果G的每一个同构于H的导出子图仅有一个中心且度至少为n/2,或存在两个中心度和至少为n,那么我们称G是H-p-重的.我们刻画了使得任意2-连通爪-o-重R-p-重图是Hamilton的所有连通图R.图G被称为是1-坚韧的,如果对任意顶点割S,G-S的分支数不超过|S|.显然所有Hamilton图都是1-坚韧的.在第六章我们考虑了 1-坚韧图的Hamilton性的禁止子图条件.我们几乎找到了所有的图R:使得任何阶至少为3的1-坚韧无R图是Hamilton的.在本论文的第七章和第八章,我们考虑了禁止子图条件和重子图条件下有关图的Hamilton性的一些相关性质.第七章研究了图的最长圈经过大度顶点的性质.对于给定的常数α ≤ 1,我们考虑对于什么样的子图R,一个2-连通图G是无R的可以保证G的任意最长圈都经过所有度至少为αn+ O(1)的顶点.我们完整刻画了满足这种性质的连通子图R.一个图的2-正则生成子图称为这个图的2-因子.Faudree等在2008年刻画了所有这样的连通图对{R,S}:使得任意2-连通无R无S图含有2-因子.在第八章我们讨论了图中2-因子的存在性的-o-重子图对条件.我们完全刻画了所有这样的子图对{R,S}:使得任意2-连通R-o-重S-o-重图含有2-因子.最后一章对本论文的工作做了一个简要总结,并提出了一些有待进一步考虑的问题.