图中因子存在性的局部性条件

This project focuses on the research of the factors of a graph: Hamiltonian cycle,2-factors and even factors with a bounded number of components, and connected even factors with a bounded maximum degree.This project studies the local conditions for the above factors and the local conditions for their equivalence.This project tries to use the local k-Hourglass properties and the P(l,k) properties to study the Matthews and Sumner's conjecture (every 4-connected claw-free graph is Hamiltonian) and the Saito's conjecture (every graph of order at least three with the local Chvátal-Erd?s condition is Hamiltonian); This project probes into the problem that every connected and locally connected graph has a connected even factor with a bounded maximum degree. It will provide some new methods and new contents of the research. This project tries to give a local closure operation for the K(1,n)-free graphs (where K(1,n) is the complete bipartite graph with two parties of orders 1 and n, respectively). It tries to extend those results of claw-free graphs to one of generic graphs. Generally, it is NP-complete to determine whether a graph has the above factors and it shows that this project is important. We shall apply ourself to seek for some conditions that may judge whether those sparse graphs (i.e., with a few number of edges) have the above factors.This will provide a new content of this kind of research.

本项目研究图的因子:哈密尔顿圈、有界定分支个数的2-因子及偶因子、有界定最大度的连通偶因子。本项目研究图中这些因子存在性的局部性条件，探讨它们等价的局部性条件。本项目试图用k-Hourglass局部性质,P(l,k)局部性质来探讨Matthews and Sumner猜想(每个4连通无爪图是哈密尔顿的)及Saito猜想(每个满足局部Chvátal-Erd?s条件的图是哈密尔顿的)并研究每个满足连通且局部连通的图是否有一个界定最大度的连通偶因子的问题,从而为图的因子存在性研究注入新的研究方法与研究内容。 本项目试图给出能够处理一般禁用子图(即不包含二部图K(1,n)为导出子图)的局部闭包运算,尝试将无爪图的结果拓展到一般图上。 一般来说,上述因子的存在性问题是NP-完全困难的,这表明了本项目的研究意义。本项目致力于寻找能判断稀疏图的局部性条件,为研究工作注入新内容。

本项目考虑了图的因子存在性的局部化条件。本项目分别从图的因子存在性的禁用子图条件,迭代线图的性质原图刻画,无爪图的最小度条件等几个方面得到了一系列的研究结果。我们考虑了具有界分支个数的偶因子，推广了一些现有结果，尤其是利用图的局部性质来刻画图的哈密尔顿性，这些结果推广了现有的关于图的哈密尔顿性的局部性条件，将禁用子图与图的局部性质结合来考虑图的性质，它推广了传统的局部性条件，这方面的结果具有创新性。我们也考虑了迭代线图的存在界定分支个数的偶因子的原图特征刻画，这个特征表明我们可以利用原图来刻画迭代线图的界定分支个数的偶因子，避免了高迭代线图给研究带来的不便，从而使得我们考虑问题变得更加直接直观，由此我们得到了一些精确界，这是主要便利的创新之处。我们还利用最小度考虑了无爪图的哈密尔顿性，解决了目前存在的一些猜想，得到了对于任意的只要最小度不大于它的介的k分之一倍，那么问题可以归结为考虑有限个顶点的图是否存在生成闭迹，而这是可以用计算机来计算出来的。而一般问题则是没有有效算法的。我们的结果发表在图论顶级杂志<组合B>上。