有向图中点不交圈的存在性参数

The problem of vertex-disjoint cycles in digraphs is the natural generalization of the Hamilton problem, it is a fundamental problem in graph theory. The existence of vertex-disjoint cycles plays an important role in structure, complexity and algorithm in networks. This project will look for some sufficient conditions for the existence of vertex-disjoint cycles in digraphs which contains degree conditions and forbidden subgraph conditions. Firstly, we expect to solove the problem posed by Henning and Yeo, that is, to investigate whether there exists two vertex-disjoint cycles with different length in a 3-regular bipartite digraph . Secondly, we want to characterize the structure of 4-arc-dominated digraphs and give partially supporting for an open problem, which posed by Lichiardopol in the 20th British combinatorial conference, here, 4-arc-dominated digraphs are oriented digraphs such that every arc is dominated by a vertex with out-degree exactly four; Thirdly, by applying theoretical proofs and constructing counter-example, we also determine the forbidden subgraphs for the existence of vertex-disjoint cycles in a given digraph, which has been given minimum out-degree and girth; Finally, since arc-disjoint cycles can been viewed as weakened form of vertex-disjoint cycles, we study the maximum number of vertex-disjoint cycles in regular digraphs, because N. Alon posed a conjecture which concers the relation bewteen vertex-disjoint cycles and arc-disjoint cycles in regular digraphs.

有向图中的点不交圈问题是哈密尔顿问题的自然推广，是图论研究中的一个基本问题。点不交圈的存在性在网络的结构、复杂性及算法实现等方面也有着重要的应用。本项目主要研究有向图中点不交圈的存在性充分条件，包括度条件和禁用子图条件。首先，研究有向3-正则二分图中是否存在两个长度不同的点不交有向圈，解决Henning和Yeo提出的一个猜想; 其次，拟完整刻画4-弧控制有向图的结构，部分地回答Lichiardopol在第20届英国组合会议提出的公开问题, 其中，4-弧控制的有向图指的是每条弧都被某个出度为4的点控制的定向图；再次，通过理论证明和构造反例，确定给定最小出度和围长的有向图中点不交圈存在的禁用子图；最后，由于弧不交问题是点不交问题的弱化，拟研究正则有向图中的点不交圈的最大个数, 考虑N. Alon等人提出的关于揭示正则有向图中点不交圈与弧不交圈之间的关系的猜测。

图上点不交圈的存在性问题是图论研究中的基本问题之一. 本项目主要围绕有向图上点不交圈的参数展开研究，主要参数包括度条件按以及极值参数条件. 本项目的主要研究内容如下：首先，研究了有向图中点不交长为4的有向圈存在性, 把简单有向图转化为标准多重图研究；其次，确定了二部图上点不交双弦圈的存在性, 探索给出了最好可能的最小度条件；再次，研究了有向二部图中任意长度的点不交有向圈分解的存在性，完整的给出了构造性证明；最后，研究了非均衡二部图中存在点不交弦圈的边参数条件，提出了进一步研究的问题.