有向图的泛弧和点不相交圈相关问题的研究

The structure of digraph is an important research field in graph theory, and the existence of universal arcs and vertex-disjoint cycles is an important branch of digraph structure problem, which is closely related to graph factor theory, graph coloring problem and so on. The project is mainly focus on the existence of universal arcs and vertex-disjont cycles in digraphs, and there are so many problems unsolved in this area. Firstly, this project will discuss the existence of universal arcs in digraphs under strongly connected and cycle-connected conditions, and furthermore study the number of univesal arcs in order to find as many universal arcs as possible. In addition,we also study another important structure of digraph,namely the existence of vertex-disjoint cycles, trying to solve or partially solve problems related to the Bermond-Thomassen conjecture. What’s more, we consider the length of cycles and study vertex-disjoint cycles with given length in digraphs, trying to find the best degree conditions. The study of this project involves combinatorial mathematics, computer networks, transport and bio-information science and other disciplines. The solution to this project is of great significance to the development of combinatorial mathematics, graph theory, computer networks, transportation industry and other disciplines.

有向图的结构问题是图论的一个重要的研究领域，而泛弧和点不相交圈的存在性是有向图结构问题的一个重要分支，它和图的因子理论及染色问题等有着非常密切的关系。本项目主要研究有向图的泛弧和点不相交圈的存在性，关于这个课题还有很多问题没有解决。首先，本项目研究强连通、圈连通等条件下有向图泛弧的存在性，深入讨论有向图中泛弧的数量，力求找到尽可能多的泛弧。其次，我们还研究有向图的另一种重要结构，即有向图中点不相交圈的存在性，试图解决或部分解决Bermond-Thomassen 猜想的相关问题。最后，我们考虑圈的长度，研究有向图中点不相交的具有指定长度的圈，力求寻找最好的度条件。本项目的研究涉及到组合数学，计算机网络，交通运输及生物信息学等学科，问题的解决对组合数学，图论，计算机网络及交通运输业等的发展都有重要的意义。

围绕有向图的泛弧和点不相交圈相关问题，我们首先研究了不同度条件下图中点不相交圈的存在性，在这个基础上考虑了度条件下标准重图中点不相交圈的存在性，并首次系统研究了三部图和三部重图中点不交的圈，把有向图的部分结果推广到重图中。接着，我们研究了度条件很弱的情况下，图包含一些点不相交的子图（如K4¯）的问题，并得到了最小度的最好下界。此外，我们利用公平划分来研究恰有三个主特征值的单圈图类，同时利用最大平均度研究了图的均匀和列表均匀染色问题。最后，我们考虑了交换交叉立方体的连通性和超连通性。项目执行期间，我们与国内外学者深入交流，参加国内外学术会议并作报告，加强了与国内高校间的交流和合作。我们圆满完成了研究计划，取得了一系列的具有独创性的结果。本项目的研究涉及到组合数学，计算机网络，交通运输及生物信息学等学科，问题的解决对组合数学，图论，计算机网络及交通运输业等的发展都有重要的意义。