重子图条件下图的Hamilton性及相关问题

发布时间：2018-03-28 21:26

  本文选题：禁止子图　切入点：重子图　出处：《西北工业大学》2016年博士论文

【摘要】：如果一个图中含有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-因子.最后一章对本论文的工作做了一个简要总结,并提出了一些有待进一步考虑的问题.
[Abstract]:If there is a Hamilton circle map, the map after all vertices in the circle, then this map is called Hamilton. This paper studies a class of sufficient conditions of Hamilton graph, graph baryon generalization of Hamilton, Bedrossian and Faudree et al on the map of the forbidden subgraph conditions the conclusion. This paper is based on the following questions: we have known some forbidden subgraphs in the graph structure, can guarantee the picture is Hamilton. If we allow these sub graph structure exists, then the limit of what kind of conditions in this subgraph structure, can still ensure the picture containing Hamilton ring? Let G be a graph. For a given graph H, if G contains no induced subgraph isomorphic to H, then we say that G is H (or H is forbidden subgraph of G).1991 Bedrossian in his doctoral dissertation depicts a connected graph of the {R like this ,S}:浣垮緱浠讳綍2-杩為

本文编号：1678107