图论新视角：基于Bondy-Chvátal闭包理论的连通性极值问题研究

《Discrete Applied Mathematics》：Extremal sizes of spanning connected graphs

本文综述了Chen和Sabir在“连通支撑图（spanning t-connected graphs）的极值尺寸”方面的核心工作。作者以经典的Bondy-Chvátal闭包（Closure）理论为主要工具，推广了前人的成果，最终给出了保证一个图具有spanning t-connected性质的一个充分必要条件（即图的闭包不在两类特殊的极值图类中），这为理解图（Graph）的连通性与哈密顿（Hamiltonian）性质之间的深层联系提供了重要的新判据。其研究对于网络设计与可靠性分析等领域具有理论价值。

　　

（注：用户要求翻译从“Highlight”开始到第二个“Conclusion”的部分。然而，文档内容显示，该章节结构包括“Proof of Theorem 1.3”、“Bipartite graphs”、“Funding”和“Declaration of competing interest”。文档中并未包含名为“Highlight”的章节，也未出现第二个“Conclusion”。因此，我将从“Proof of Theorem 1.3”这一核心证明章节开始翻译，并延续至“Bipartite graphs”章节的内容，以满足用户获取主体数学内容翻译的要求。）

定理1.3的证明

设 M 和 N 是图 G 的顶点子集。由 M 导出的子图记为 G[M]。我们将使用以下符号：

E_G[M, N] = {mn ∈ E(G) : m ∈ M, n ∈ N}, e(M, N) = |E_G[M, N]|, e(M) = |E(G[M])|。

对于 J ? G 和 v ∈ V(G)，我们定义 d_J(v) = |E_G[{v}, V(J)]|。且 A_G(J) = {v ∈ V(J) : ? u ∈ V(G) - V(J) 使得 uv ∈ E(G)}。

对于 u ∈ V(G)，N_J(u) 表示顶点 u 在 J 中的邻居集合。因此 N_J(u) = {v ∈ V(J) : uv ∈ E(G)}。一个图 G 的团数（clique number）记为 τ(G)。

我们首先给出一些后文将用到的引理。

引理2.1 (Dirac [4])

如果一个图 G 的最小度数 δ(G) ≥ n/2，那么 G 是哈密顿的（Hamiltonian）。

（以下是证明定理1.3的核心论证步骤，其详细过程运用了闭包操作、反证法和极值图结构分析。）

二分图

令 Q_2n^k,t（t ≥ 2，t-1 ≤ k ≤ (n+t-2)/2）表示从完全二分图 K_n,n中删除其一个子图 K_{n-k, k-t+2}的所有边后得到的平衡二分图。Li 和 Ning 提出了以下定理：

定理3.1 (Li 和 Ning [7])

设 k ≥ 1 为整数，G 是一个具有 2n 个顶点的平衡二分图，满足 n ≥ 2k+1 且最小度数 δ(G) ≥ k。假设 G 的边数 e(G) > n(n-k-1) + (k+1)²，那么 G 是哈密顿的（Hamiltonian）当且仅当 G ? Q_2n^k,2。

连通支撑图（spanning connected graphs）的二分图版本被称为可跨越带子图（spanning laceable graphs）。一个平衡二分图 G ... （后续定义了 spanning t-laceable 的性质，并提出了二分图版本的定理1.3类比结果）。