图中圈结构及特型支撑子图研究

Finding the length of a longest cycle in a graph is a fundamental, yet difficult, problem in graph theory. Indeed, the subproblem of determining whether a graph contains a hamiltonian cycle is a classic NP-complete problems. Therefore, a feasible way to work on this problem is to consider special classes of graphs. In 1988, Malkevitch conjectured that if a 4-connected planar graph contains a 4-cycle, then it is pancyclic. In this project, we will work on this conjecture and its related problems. The graph families related to our research include plane graphs, K_(3,t)-minor free graphs and some dense graphs. Instead of finding cycles with given lengths directly, we will verify whether a given graph contains a spanning Halin subgraph; When a spanning Halin subgraph is not ensured, we are interested to know when a graph contains a homomorphically irreducible spanning tree, or a large wheel as a minor. A large wheel-minor gives much more structure properties than a cycle does. For example, if a graph contains a large wheel-minor, then it contains both a long cycle and a large minimal edge-cut. This expanding from finding a long cycle to finding a large wheel-minor is a big step forward in advance the knowledge and understanding in the field.

确定图中最长圈的长度是图论中最基本、最困难的问题之一。事实上，该问题的子问题--“确定一个图是否包含一个哈密尔顿圈”就是一个经典的NP-完备问题。 因此，研究最长圈问题的一个可能途径是在一些特殊图类中研究该问题。1988年，Malkevitc猜想“所有含4-圈的4-连通平面图都是泛圈图”。本课题将围绕该猜想及其相关问题进行探讨，研究所涉及的图类包括平面图、不含K_(3,t)-minor图和某些稠密图。 有别于直接寻找给定长度的圈的方法， 我们将探讨一个给定图是否包含支撑 Halin子图；当给定的图不含支撑 Halin子图时，我们将研究该图在何条件下包含一个同胚不可约支撑树或大型轮图子式。一个大的轮图子式往往比一个圈包含更多的图结构信息，例如：如果一个图包含一个大的轮图子式，那么该图既包含一个长圈，也包含一个大的极小边割集。这一由寻找长圈到寻找大轮图子式的转变是图结构研究的一个重要进步。

子图存在性问题是图论研究的一个热点。本项目利用色数、独立数、连通度、最小度等图中基本参数，对子图存在性问题进行了深入探讨，在边色数临界重图的结构性质、平面图邻接矩阵的第二大特征值的重数、 边色数临界重图的平均度、3-连通图中支撑Halin子图的存在性、稠密图的密接性、t-色图中K_t-minor的存在性、图中具特定性质的支撑树的存在性、二部图的圈结构等方面取得重要进展，共完成研究论文14篇，其中9篇被SCI收录。主要结果如下：(1) 对边色数临界重图的结构性质进行了深入研究，在著名的Goldberg-Seymour猜想研究中取得重要进展，相关结果在Journal of Combinatorial Theory Series B 139 (2019) 上发表； (2) 对平面图结构进行了深入研究，得到(外)平面图G的邻接矩阵的第二大特征值的重数与G的最大度之间的密切联系, 相关论文在Journal of Graph Theory 98 (2021) 上发表；（3）对图的色指数与其平均度的关系进行了深入探讨,完成研究论文一篇, 在Discrete Mathematics 342 (2019)上发表；（4）利用禁用子图，对3-连通图中支撑Halin子图的存在性进行了深入研究，完成研究论文3篇；（5）对稠密图的密接性及Hadwiger关于t-色图中K_t-minor的存在性猜想进行了深入研究，完成研究论文2篇；(6) 对图中特型支撑树的存在性进行了卓有成效的研究，在SCI期刊发表论文2篇； （7）对二部图的最小边比数与其圈结构的关系进行了深入探讨，证明了最小边比数至少为1/2的二部图为路二弱偶泛圈图或同构于G2n,4，相关论文在Applied Mathematics and Computation 377（2020）发表； (8) 对树中点的度与其平方图中路因子的存在性之间的关系进行了研究，相关结果在Graphs and Combinatorics 36 (2020)上发表。本项目的研究拓展了子图存在性问题研究的内涵，有利于我国图论研究与世界进一步接轨.