图（超图）的子图存在性问题研究

The existence of subgraph is a core problem of structural graph theory. This project includes the following three topics: the existence of topological minors and contractible subgraphs of k-connected graphs, algorithms of power domination problems and the upper bounds for power domination numbers in graphs, partition edge-colored hypergraphs by cycles or paths. The main content of the project is as follows. (1) Based on Yu's techniques for solving the Kelmans-Seymour Conjecture, we shall research on the existence of K_5^- topological minors and contractible subgraphs in 4-connected graphs. We shall also study the sufficient conditions for 3-connected graphs containing a K_5^- topological minor. (2) Considering the conjecture presented by Dorbec et.al for the upper bound of k-power domination number in regular graphs, we shall give good upper bounds of k-power domination number for 4-regular and general r-regular graphs. We shall also study algorithmic complexity on power domination and other relevant domination problems in graphs, especially study polynomial-time algorithms in subclasses of chordal graphs. (3) We shall study the Bustamante and Stein's cycle-partition conjecture on 2-edge-colored complete hypergraphs, and also study the Gyárfás and Sárközy's loose cycles partition conjecture on non-complete hypergraphs. We hope to make breakthrough on these cycles partition conjectures.

子图存在性问题是结构图论的核心问题。本项目主要考虑三方面的问题：k-连通图中拓扑子式和可收缩子图的存在性、电力控制集算法和电力控制数的上界、边染色超图的圈或路划分。其核心内容包括：一、在郁星星等人解决Kelmans-Seymour猜想的方法基础上，研究4-连通图中存在K_5^-拓扑子式及可收缩子图的存在性问题，同时研究3-连通图中存在K_5相关拓扑子式的充分条件；二、围绕Dorbec等人关于k-电力控制数上界的猜想展开研究，希望得到4-正则和一般r-正则图的k-电力控制数好的上界，同时研究电力控制集及相关控制集的算法复杂性以及在弦图子图类上的多项式时间算法；三、研究Bustamante和Stein关于2-边染色一致完全超图的圈划分猜想以及Gyárfás和Sárközy关于非完全超图的线性圈划分猜想，希望在这些圈划分猜想上取得突破性进展。

子图存在性问题是结构图论研究的核心问题之一，通常与生产生活中的优化问题密切相关，也是图论算法研究的重要基础。围绕子图存在性本项目主要研究：图的拓扑子式等子图存在性问题、控制集问题、2-分辨集问题。项目取得的主要成果如下。.一、在拓扑子式等子图存在性问题方面，证明了4-连通图中K_5^--拓扑子式的存在性，该结果在Kelmans-Seymour猜想的基础上降低了连通度要求，一定程度上有助于Hajos猜想k=5情形的解决；用全新的方法证明了Mader猜想对于直径较小的树、caterpillar和generalized star都是成立的，为Mader猜想的进一步研究提供了新思路；研究了一些经典的子图极值问题，证明了两个顶点不交团的Turan数，给出了围长不超过k的2-连通图中完全二部子图K_{r,s}个数的极值刻画，对于禁用小的完全二部子式、长圈、短圈等情形给出了一系列谱极值刻画的结果。.二、在控制集问题方面，证明了Goodard和Henning等人于2009年提出的配对控制集上界猜想对无爪图是成立的，证明中用到的匹配边权值的组合分配技巧为完全解决该猜想提供了思路；通过一系列反例彻底否定了Dorbec等人于2013年提出的正则图电力控制集上界猜想，并且对一般的k-正则图给出了该问题紧的上界；利用动态规划思想首次给出了带权值树图k-电力控制集问题的线性时间算法，为赋权图的控制集问题研究提供了新思路。.三、在2-分辨集问题方面，证明了最小度至少为2的k-边增树最小2-分辨集的大小不超过2k+1，大大改进了陈旭谨等人之前的结果；建立了超立方体的2-分辨集问题与硬币称重问题的桥梁，由此解决了一系列公开问题和猜想，给出了硬币称重问题一些新的上界；给出了汉明图的2-分辨集问题和折叠超立方体的度量维数问题的渐近解，并推翻了折叠超立方体的度量维数问题的一个猜想；通过与Lindstrom方法的联系，给出了求解超立方体2-分辨集问题的有效算法，该算法远远优先于现有算法；并且证明了2-分辨集问题限定在分裂图、二部图、余二部图上是NP-难的。