局部半完全有向图的分解及相关问题的研究

The decomposition of digraphs is always the topic in graph theory, especially for tournaments and their generalizations. A lot of breakthrough results have been achieved on the decomposition and the related problems of tournaments. As the important generalization of tournaments, locally semicomplete digraphs have been get extensive attention. Because of the more complicated structure, some results on tournaments have not yet been extended to locally semicomplete digraphs and some open problems on the decomposition have not been solved. In this project, we shall investigate detailedly several important decomposition and related problems on locally semicomplete digraphs, including the existence of arc-disjoint cycles and paths and the decomposition of the strong spanning subdigraphs and, make the real progress towards the conjectures “Every 3-strong local tournament has two arc-disjoint Hamiltonian cycles.” and “If the minimum semi-degree of a k-arc-strong locally semicomplete digraph is sufficient large, then it has k arc-disjoint strong spanning subdigraphs.” posed by Bang-Jensen et al. in 2012.

有向图（特别是竞赛图及其推广图）的分解是图论的一个重要研究课题。对竞赛图的分解及其相关问题，人们已经取得了许多突破性的成果。局部半完全有向图是竞赛图的最重要的一类推广图，在近二十年得到了广泛关注。但因其结构的复杂性，许多有关竞赛图的结论还没有推广到这个图类上，许多关于分解的公开问题还没有得到解决。本项目将系统研究局部半完全有向图的若干重要分解及相关问题，包括弧不相交的圈路的存在性和强连通生成子有向图分解等问题，并对Bang-Jensen等人在2012年提出的下面猜想取得实质性进展：“每个3强连通的局部竞赛图包含两个弧不相交的哈密尔顿圈”和“如果k弧强连通的局部半完全有向图的最小半度足够大，那么它包含k个弧不相交的强连通生成子有向图。

有向图（特别是竞赛图及其推广图）的分解是图论的一个重要研究课题。本项目研究了竞赛图的一类推广图——局部半完全有向图的分解及相关问题。通过研究局部半完全有向图的某些图指标，包括连通度、通用弧、竞争图等，部分解决了Bang-Jensen和Huang在2012年提出的猜想：“每个3强连通的局部竞赛图包含两个弧不相交的哈密尔顿圈。”并利用类似的方法，对某些竞赛图的推广图，包括多部竞赛图、超竞赛图，k准传递有向图等的竞争图、二次外邻、哈密尔顿路等问题进行了研究，将竞赛图的相关结论推广到了这些图类上。共发表论文13篇，其中8篇发表在SCI收录期刊。培养了6名硕士研究生，另有2名在读研究生。