次模性在极小图类结构研究中的应用

Applications of Submodularity in the Structure Analysis of Minimal Graphs

摘要: 本文运用邻域函数的次模性，结合关键集、紧集等概念，构建了一种分析极小图类最小度的统一 方法，并运用该方法证明了极小 k -可扩二部图中必然存在度数为 k+1 的顶点，以及极小强 k- 连通图中必然存在出度数/入度数为 k 的顶点。本研究提出的方法为极小图结构的分析提供了新的 组合论视角，为极小临界图最小度的猜想提供了理论支撑。

Abstract: In this paper, we use the submodularity of neighbourhood functions, combined with the concepts of key set and tight set, to develop a unified method for analysing the minimum degree of minimal graphs, and apply the method to prove the existence of vertices of degree k + 1 in minimally k-extendable bipartite graphs as well as vertices of out-degree or in-degree k in minimally strongly k-connected graphs. The meth- ods proposed in this work provide a new combinatorial perspective for the structure analysis of minimal graphs, and provide theoretical support for the conjecture on the minimum degree of minimal critical graphs.