类竞赛图的结构性质研究

Tournaments are firstly studied in digraphs and are useful in many fields. At present, there are a lot of results on tournaments. Generalizations of tournaments are also called tournament-like digraphs. Tournament-like digraphs, which contain k-quasi-transitive digraphs and arc-locally in-semicomplete digraphs etc, are a hot area of research for several years. Structural properties of digraphs contribute to study other parameters of digraphs. Hamiltonicty is related to the problem of the longest path(cycle) and pancyclicity. Kernels and kings are closely related to the diameter and the radius of digraphs. In this item, we will study the above problems on tournament-like digraphs. In detail, first we study the structure of k-quasi-transitive digraphs and arc-loaclly in-semicomplete digraphs; second we also will give the sufficient and necessary conditions for k-quasi-transitive digraphs and arc-locally in-semicomplete digraphs to be hamiltonian; finally we will study a conjeture on (k+1)-kernels in k-quasi-transitive digraphs and study the existence of k-kings in k-quasi-transitive digraphs.

竞赛图是得到研究最早且结果最丰富的一类有向图，其理论和方法已经渗透到许多学科和领域。竞赛图的推广图，也称为类竞赛图，包含k准传递有向图和弧局部内半完全有向图等。它是近年来有向图领域的研究热点之一。图的特征刻画能够对研究它的其它性质和参数提供帮助；Hamilton性问题与有向图中的最长路、最长圈、泛圈性等问题有一定的联系，而且Hamilton性问题本身的计算复杂性也是值得关注的；核和王与有向图的直径、半径等问题密切相关。所以刻画图的特征，研究其Hamilton性以及图中的核和王等问题是有意义的。本项目将综合运用图论、组合优化及数学规划的方法来研究类竞赛图的上述问题，具体如下：首先刻画k准传递有向图和弧局部内半完全有向图的结构特征；其次研究k准传递有向图和弧局部内半完全有向图的Hamilton性；最后解决“k准传递有向图中存在k+1核”这个猜想，并研究k准传递有向图中k王的存在性。

类竞赛图，也称为竞赛图的推广图，是有向图中一个非常重要的图类，拥有大量的难题和猜想。本项目主要研究了类竞赛图的结构性质，并取得了下述成果：.1. 研究类竞赛图的Hamilton性。我们证明了当k为大于等于4的偶数时，直径大于等于k+2的强连通k准传递有向图中存在Hamilton路；给出了平衡二部有向图中存在Hamilton圈的控制对条件；部分解决了二部有向图中关于最长圈的一个猜想。.2. 刻画类竞赛图的结构。我们刻画了直径大于等于k+2的强连通k准传递有向图的结构特征。.3. 研究类竞赛图中(k+1)核和k王的存在性。证明了“k准传递有向图中存在k+1核”这个猜想；给出了k准传递有向图中存在k王的充要条件；给出了强连通的k传递有向图中存在k-1核的充要条件。.. 本项目的研究在一定程度上推动了类竞赛图的研究进展。项目执行期间共发表学术论文10篇，参加学术会议6次，培养硕士研究生2名。