强连通多部竞赛图中的泛圈性研究

The pancyclicity problem of graphs is the natural generalization of the Hamilton problem. In recent years, the pancyclicity problem of graphs has been an important topic in graph theory. Tournaments are the best structure class of directed graphs and there are many results on its pancyclicity. Multipartite tournaments, as the natural generalization of tournaments and as a class of very important digraphs, have been get extensive attention. However, the results on pancyclicity in multipartite tournaments are still very few. In general, multipartite tournaments are not pancyclic, and nor vertex pancyclic. The discuss for pancyclicity of multipartite tournaments has focused almost entirely in regular and almost regular multipartite tournaments. In this item, we will mainly research the relation between cycles and some parameters of strong multipartite tournaments, such as the number of partite sets、connectivity、independence number、minimum degree、maximum degree、global irregularity、local irregularity and so on, and then obtain some conditions for strong multipartite tournaments to be pancyclic、vertex- pancyclic and to contain pancyclic arcs、 out-arc pancyclic vertices. In addition, we will try to prove the conjecture posed by Yeo in 1999 " Each regular 4-partite tournament is vertex-pancyclic" and the conjecture posed by Volkmann in 2002 "Each almost regular 4-partite tournament is vertex 4-pancyclic".

图的泛圈性问题是Hamilton问题的自然推广。近年来，图的泛圈性问题已经成为图论中一个重要研究课题。竞赛图是有向图中结构最好的一类图，其泛圈性方面已有很多结果。多部竞赛图作为竞赛图的自然推广，也作为有向图中的一个非常重要的图类，也受到了广泛的关注，但其泛圈性方面的结果却很少。一般来说，多部竞赛图不是泛圈的，更不是顶点泛圈的。对多部竞赛图的泛圈性问题的研究，几乎集中在正则和几乎正则多部竞赛图中。本项目将主要研究强连通多部竞赛图的圈与一些参数，如部集数、连通度、独立数、最小度、最大度、全局非正则度、局部非正则度等指标之间的联系，进而获得强连通多部竞赛图泛圈、顶点泛圈以及它包含泛弧、外弧泛圈顶点的若干条件，并试图证明Yeo在1999年提出的一个猜想: "每个正则4-部竞赛图是顶点泛圈的"和Volkmann在2002年提出的猜想："几乎正则4-部竞赛图是顶点4泛的"。

多部竞赛图，由于它的应用背景，而成为有向图中一个非常重要的图类。本项目拟研究的问题是强连通多部竞赛图的泛圈性，主要包括多部竞赛图的泛圈、顶点泛圈、弧泛圈、泛圈顶点、泛弧数、外弧泛圈顶点等内容。. 竞赛图是特殊的多部竞赛图，其泛圈性方面已有很多结果，而对于一般的多部竞赛图的泛圈性研究，则是相当困难的问题。在我们的前期工作中，解决了Yeo在2005年提出的关于竞赛图外弧泛圈顶点方面的重要猜想。本项目中，我们在前期工作的基础上，首先研究了强连通竞赛图的顶点的外弧泛圈性，得到了比Yeo猜想更一般的结果。其次，我们研究了多部竞赛图中的圈问题。2006年，Volkmann研究了3-部竞赛图中的圈并提出一个重要猜想，然而这个猜想多年来没有得到解决，我们在小参数的情形下解决了Volkmann的猜想。然后我们研究了多部竞赛图的弧泛圈性，推广了Moon的相关结果。1999年，郭余宝教授提出外路的概念，以自然的方式推广了有向图中的圈。本项目也深入研究了正则和几乎正则多部竞赛图中顶点和弧的泛外路性，给出了顶点和弧泛外路的若干充分条件，有的结果推广了郭余宝教授的相关结果。最后，我们研究了正则4-部竞赛图的泛圈性，给出了正则4-部竞赛图是泛圈的一个充分条件。.项目执行期间共发表学术论文12篇，参加学术会议6次，培养硕士研究生3名。.