图中包含特定元素的子图结构研究

The research of subgraph structures containing given elements in a graph is a hot topic in the research of graph theory. It not only has important theoretical significance, but also enjoys strong applicability in theoretical computer science, biological science and operations research. Based on the research of structure graph theory we have long focused on, and proceeding from the three basic parameters of graphs including connectivity, minimum degree and minimum degree sum of non-adjacent vertices, this project is intended to make a profound research on the subgraph structures containing given elements in a graph. By employing such new concepts and techniques as“good sets”and“auxiliary bipartite graphs”that are closely related with a longest cycle C of G and components of G-C, we will investigate the length of a longest cycle passing through some given elements in a graph; and by introducing the latest methods and techniques such as tree exchanges, co-vertices，component expansions and assigned vertices, we will further explore the relationship between minimum degree, minimum degree sum of non-adjacent vertices，connectivity and the existence of vertex disjoint connected subgraphs in a graph containing partitions of a given vertex subset, and apply it to the research of the minimum counterexample of the Hadwiger's Conjecture. As a result, the project will contribute to the earlier solution to the Locke-Zhang open problem and the Hadwiger's Conjecture on the existence of K_t-minor in t-chromatic graphs, which will help to promote the research on graph structure theory in China to the international level.

图中包含特定元素的子图结构是图论研究的热点之一。对其进行研究不但有重大的理论意义，而且在理论计算机科学、生命科学和运筹学中有很强的应用背景。本项目拟在我们长期从事的结构图论研究的基础上，从连通度、最小度、不相邻点最小度和这三个图中基本参数出发, 对图中包含特定元素的子图结构做更进一步的探讨。我们将利用与最长圈C以及G-C的分图密切关联的“好集合”、“辅助二部图”等新概念和新技巧，研究图G中过特定元素的最长圈长度；通过引入树变换、余顶点、分图扩张、配点等新概念和新方法, 研究最小度、不相邻点最小度和、连通度与图中包含特定子集划分的点不交连通子图的存在性之间的关系, 并将其应用于Hadwiger猜想的极小反例研究。本项目的研究将推进Locke-Zhang所提出的公开问题以及Hadwiger关于t-色图中K_t-minor的存在性猜想的早日解决，有利于我国结构图论研究与世界进一步接轨。

子图存在性问题是图论研究的一个热点。本项目利用连通度、最小度等图中基本参数，对子图存在性问题进行了深入探讨，在图中过特定子图的最长圈、 图中包含特定子集划分的点不交连通子图的存在性、二部图的圈结构和路结构、平方图中路因子的存在性、图中特型支撑树的存在性、图谱和图中结构的拓扑性质等方面取得重要进展, 共发表研究论文21篇，其中20篇被SCI收录。主要结果如下：(1) 对图中过特定子图的最长圈问题进行了卓有成效的探讨，在Locke和张等人于1991年提出的公开问题及其推广上取得重要进展，相关论文在Journal of Graph Theory 87(2018)和Graphs and Combinatorics 36(3) (2020）上发表； (2) 在图中包含特定子集划分的点不交连通子图的存在性研究中取得重要进展，相关成果应邀在第九届全国组合数学与图论大会上报告；(3) 对二部图的最小边比数与其奇偶泛路连通性之间的关系进行了深入探讨，证明了所有最小边比数至少为1/2的二部图都是奇偶泛路连通图，相关论文在Applied Mathematics and Computation 377（2020）发表； (4) 对树中点的度与其平方图中路因子的存在性之间的关系进行了研究，相关结果在Graphs and Combinatorics 36 (6) (2020)上发表；(5) 对图中特型支撑树的存在性进行了卓有成效的研究，在SCI期刊发表论文3篇； (6) 对图的各类谱和图中结构的其它几类代数特征进行了深入探讨，在 SCI期刊发表论文12篇。本项目的研究拓展了子图存在性问题研究的内涵，有利于我国图论研究与世界进一步接轨。