图与有向图中点不交子图存在性问题的研究

The existence of vertex-disjoint subgraphs in graphs and digraphs is an important research subject in structural graph theory and combinatorial optimization, and is closely related to community partition in complex networks. In this project, we mainly focus on vertex-disjoint cycles of graphs and digraphs, the existence conditions of vertex-disjoint subgraphs and path partition problems in digraphs, which were considered by Alon, Erdős, Bollobás, Thomassen et al. For the existence conditions, we intend to consider minimum degree, degree sum conditions, partial degree, Fan-type degree, implicit degree. And for the subgraphs, we will consider stars, cycles and chorded cycles. In this project, we devote to solving several problems and conjectures. Actually vertex-disjoint subgraphs problem is an extension of Hamilton cycle problem, the study of this project will promote the development of structural graph theory.

图与有向图中点不交子图存在性问题是结构图论以及组合优化中一个重要的研究方向，与复杂网络的社团划分问题有着密切的联系。我们主要研究图与有向图的点不交圈问题，不同极值性条件下点不交子图的存在性问题以及有向图的路划分问题。这里极值条件指最小度条件、度和条件、局部度条件、范-条件、隐度条件等，研究的子图包括星、圈、弦圈等。这些问题得到了Alon，Erdős，Bollobás，Thomassen等数学家的研究和关注。我们力求解决上述研究领域的几个问题和猜想，深入刻画图的结构，在图与有向图的点不交子图问题上取得实质性的进展。本项目所研究的内容也是哈密尔顿圈问题的延伸，问题的解决对于结构图论的理论发展有着重要的意义。

本项目研究了图的点不交特定子图存在性问题以及部分极值问题。关于图的点不交特定子图存在性问题，我们研究了如下几个问题：（1）图的点不交c-弦圈问题，证明了当图的点数n较大且图中任意不相邻两点的最小度和至少为n时，图可划分成k个点不交的圈，使得每个圈包含至少c条弦；（2）边临界图的Hamilton问题，证明了当最大度至少为2n/3+12时，边临界图存在Hamilton圈；（3）无星图的点不交星问题，部分解决了Fujita猜想并给出了一些反例；（4）二部图中含特定点的子图问题，给出了含特定点集的二部图包含k个点不交的圈覆盖这个特定点集的局部度条件；（5）强边染色图的彩虹Hamilton圈问题，证明了最小度大于n/2时点数为n的强边染色图存在彩虹Hamilton圈并刻画了最小度为n/2时图的结构。关于极值问题，我们研究了广义Turán问题和树的连通Turán问题，证明了当H是5-圈加一条弦时ex(n,K3,H)=Θ(n^3/2)，同时我们还证明了ex_c(n,Tk)≥nk/4−o(n)，并给出了ex_c(n,B(k,d))的确切值，这里B(k,d)指直径为d的Broom。