有向图中不相交的圈及相关问题研究

The disjoint cycle problem in digraphs (in particular, in tournaments, in multipartite tournaments and in hyper-tournaments) is an important research topic. The theory of digraphs has developed enormously. Multipartite tournaments and hyper-tournaments, which are the generalizations of tournaments, are the most attention of digraphs in recent 20 years. But because of the complexity of their structures, many results on tournaments have not been extended to the two classes of digraphs. In this item, we shall study the following problems: 1.We shall study the existence of disjoint cycles in tournaments, in particular, focus on a conjecture on the number of disjoint cycles in tournaments, which has been proposed by Bermond et al and Henning et al. 2.We shall study two conjectures on the decomposition of 2 cycle-factor in multipartite tournaments, which were proposed by Yeo and Volkmann, respectively. Furthermore, we shall also study other problems associated with the two conjectures. 3. We shall study the decomposition of 2 cycle-factor in hyper-tournaments. We have done some research of some questions of the above questions and have obtained some achievements.So we want to apply this project to do further research of the above questions to enrich the research results in the related field.

有向图(特别是竞赛图、多部竞赛图和超竞赛图)中不相交的圈问题是图论的一个重要的研究课题。对竞赛图的研究，人们已经取得了许多突破性的成果。对于竞赛图的推广图多部竞赛图和超竞赛图，在近二十年得到人们的广泛关注。但因其结构的复杂性，许多有关竞赛图的结论还没有推广到这两类图上。本项目将系统地研究以下内容：1.研究竞赛图中不相交圈存在性问题，尤其重点研究Bermond等和Henning等分别提出的关于有向图中不相交圈的个数的猜想。 2.研究Yeo和Volkmann分别提出的关于多部有向图的2圈因子分解的猜想，同时研究由这两个猜想引伸出的一些相关问题。3.研究超竞赛图上的2圈因子分解问题。申请人已经对上述问题中的部分问题做了研究，并取得了部分阶段性成果，因此我们特申请该基金对上述问题做进一步深入地研究，以丰富相关领域的研究成果。

项目申请人的重要的研究方向是有向图的类竞赛图的不相交的圈的存在性问题和无向图的连通度问题，并取得了一些研究成果。（1）首先，我们与德国亚琛工业大学的学者Vokmann教授等合作，研究正则多部竞赛图的圈因子分解问题，证明了：除特殊图外，每一个正则的多部竞赛图都包含长分别为和顶点个数减的圈因子。（2）申请者与Vokmann教授合作将猜想推广到非正则多部竞赛图类上，证明了：部集数足够多的情况下，几乎正则多部竞赛图是圈因子可分解的，并且其中有一个圈的长为。（3）申请者与清华大学的陆玫教授和山东大学的李国君教授分别合作，利用零阶Randic指标和广义零阶Randic指标，分别给出任意图和不含三圈的图是最大边连通图的充分条件。同时，申请者和陆玫教授利用逆度指标给出图是超边连通的充分条件。（4）项目组成员对有向图的哈密尔顿圈的存在性给予高度关注。主要得到以下结果：令是具有个顶点的强连通平面二部有向图。如果它的每一个控制对，有或者，则包含一个哈密尔顿圈，且这个界值是紧的。在此基础上.,部分证明了2012年J. Adamus和L. Adamus提出的猜想。我们得到的所有结果都是新的，对当前的学术研究具有一定的意义。