（p + 1）K?-饱和图的最小边数

《Discrete Mathematics》：The minimum number of edges in ( p?+?1) K 2-saturated graphs

　　

**摘要**

给定图族 ?，若图 G 不含 ? 中的任何图作为子图，但对补图 $\overline{G}$ 中的每条缺失边 $e$，图 $G+e$ 都包含某个 $F\in\mathcal{F}$ 作为子图，则称 G 为 ?-饱和的。?-饱和图中最少边数的研究是极值图论中的核心课题。

设 $(p+1)K_2$ 表示大小为 $p+1$ 的匹配。确定 $(p+1)K_2$-饱和图中的最少边数是该领域的一个基本问题，被 Faudree 等人（2011）在其综述文章中明确列为问题 9。在本文中，我们深化了对 $(p+1)K_2$-饱和图的结构分析，推导出以单个整数参数表示边数的显式公式。通过对该公式取最小值，我们确定了所有 $n\geq 2p+2$ 时的 $\mathrm{sat}(n,(p+1)K_2)$，从而在完全一般的情形下解决了问题 9，并推广了 Kászonyi–Tuza（1986）和 Zhang–Lu–Yu（2023）的已有结果。此外，通过对该公式取最大值，我们恢复了 Erd?s–Gallai（1959）关于此类图边数的经典上界。

**引言**

设 $\mathcal{F}$ 为一个图族。若图 $G=(V,E)$ 中不含 $\mathcal{F}$ 中的任何 $F$ 作为子图，但对于补图 $\overline{G}$ 中的任意边 $e$，图 $G+e$ 都包含某个 $F\in\mathcal{F}$ 作为子图，则称 $G$ 为 $\mathcal{F}$-饱和的。

对于正整数 $n$，定义饱和数为

$$\mathrm{sat}(n,\mathcal{F})\triangleq\min\{|E(G)|:|V(G)|=n,\;G\text{ 是 }\mathcal{F}\text{-饱和的}\}.$$

类似地，$\mathrm{Sat}(n,\mathcal{F})$ 表示恰好有 $\mathrm{sat}(n,\mathcal{F})$ 条边的 $n$ 顶点 $\mathcal{F}$-饱和图的集合。

1941 年，Turán [7] 引入了极值数的概念，并确定了不含 $K_r$ 的图的最大边数。此后，Erd?s、Hajnal 和 Moon [3] 将关注点转向相应的最小化问题。

Faudree 等人 [4] 对 $\mathrm{sat}(n,\mathcal{F})$ 进行了系统综述，汇集了广泛的结果、猜想与开放问题。设 $(p+1)K_2$ 表示大小为 $p+1$ 的匹配。确定 $\mathrm{sat}(n,(p+1)K_2)$，即 $n$ 阶 $(p+1)K_2$-饱和图的最少边数，是一个重要的开放问题（参见 [4] 中的问题 9）。在此背景下，自然将注意力集中在非平凡范围 $n\geq 2p+2$ 上。事实上，大小为 $p+1$ 的匹配需要 $2p+2$ 个顶点，因此当 $n\leq 2p+1$ 时，向 $n$ 顶点图添加缺失边永远无法产生 $(p+1)K_2$ 的副本。

目前已有一些部分结果。Mader [6] 证明了 $(p+1)K_2$-饱和图的结构定理：此类图要么是奇数阶完全图的互不相交并，要么是连通的且至少包含一个度数为 $|V(G)|-1$ 的顶点。该结果总结为以下定理。

**定理 1** (Mader [6])

设 $G$ 为 $n$ 阶的 $(p+1)K_2$-饱和图。若 $G$ 不连通，则 $G$ 为完全图的互不相交并，且每个完全图均含奇数个顶点。若 $G$ 连通，则 $G$ 包含一个度数为 $n-1$ 的顶点，且删除该顶点后得到一个 $pK_2$-饱和图。

饱和数 $\mathrm{sat}(n,(p+1)K_2)$ 及极值图族 $\mathrm{Sat}(n,(p+1)K_2)$ 在 $n$ 相对于 $p$ 足够大的情形下已被确定。具体而言，Kászonyi 和 Tuza [5] 证明了以下定理。

**定理 2** (Kászonyi 和 Tuza [5])

设 $n$ 和 $p$ 为正整数。若 $n\geq 3p$，则

$$\mathrm{sat}(n,(p+1)K_2)=3p,$$

且

$$\mathrm{Sat}(n,(p+1)K_2)=\{pK_3\cup(n-3p)K_1\}.$$

对于 $2p+2\leq n<3p$ 的情形，文献中尚无完整的分析，尽管已有部分相关结果。令 $k=n-2p$。Zhang、Lu 和 Yu [9] 确定了当 $n>\sqrt{n}+2p$（即 $k>\sqrt{n}$ 且 $p\geq 2$）时的 $\mathrm{sat}(n,(p+1)K_2)$ 和 $\mathrm{Sat}(n,(p+1)K_2)$。他们证明在此范围内，每个极值 $(p+1)K_2$-饱和图都是不连通的，且所有连通分支均为阶数相差不超过 2 的奇数阶完全图。其结果总结如下。

**定理 3** (Zhang、Lu 和 Yu [9])

设 $n$ 和 $p$ 为 $p\geq 2$ 的正整数，令 $k=n-2p$。假设

$$\sqrt{n}+2p\sqrt{n}$。则存在整数 $A$ 和 $B$ 使得

$$A+B=k,\quad A(2t+1)+B(2t-1)=n,$$

$$\mathrm{sat}(n,(p+1)K_2)=A\binom{2t+1}{2}+B\binom{2t-1}{2},$$

且

$$\mathrm{Sat}(n,(p+1)K_2)=\{AK_{2t+1}\cup BK_{2t-1}\}.$$

此外，Yuan [8] 证明了当 $n<\sqrt{n/2}+2p$（即 $k<\sqrt{n/2}$）时，每个 $(p+1)K_2$-饱和图必含至少一个度数为 $|V(G)|-1$ 的顶点。

然而，如上所述，确定 $(p+1)K_2$-饱和图在所有 $n$ 和 $p$ 下的最少边数的普遍问题仍未解决。我们的方法适用于所有 $n>2p$，因此自然地将问题完全一般地表述如下。

**问题 1**

对所有整数 $n\geq 2p+2$（即 $k\geq 2$），确定 $\mathrm{sat}(n,(p+1)K_2)$ 和 $\mathrm{Sat}(n,(p+1)K_2)$。

在本文中，我们给出了问题 1 的完整解答。我们识别出极值 $(p+1)K_2$-饱和图在两种行为（即连通或不连通）之间的尖锐分界。对每种情形，我们给出最少边数关于 $n$ 和 $k$ 的显式公式。

本文结构如下。第 2 节介绍记号并提供后续证明所需的预备结果。第 3 节给出本文的主要定理——定理 4，其中推导出 $\mathrm{sat}(n,(p+1)K_2)$ 的统一表达式。第 4 节阐述由主定理得出的推论，包括定理 4 如何解决问题 1 以及如何推广定理 2 和定理 3。此外，我们的框架恢复了 Erd?s 和 Gallai [2] 所得到的此类图边数的经典上界。第 5 节给出结论。

**预备知识**

本文采用图论的标准术语 [1]。所有图均为简单无向图。对 $v\in V(G)$，用 $d(v)$ 表示 $v$ 的度数。对任意顶点集 $U\subseteq V(G)$，用 $G-U$ 表示 $G$ 由 $V(G)\setminus U$ 诱导的子图。用 $\mathcal{C}(G)$ 表示 $G$ 的连通分支集合。用 $\nu(G)$ 表示 $G$ 的匹配数（即最大匹配的大小）。

**定义 1**（万邻点）

若图 $G$ 中的顶点 $v$ 与 $G$ 中所有其他顶点均相邻，即其度数为 $|V(G)|-1$，则称 $v$ 为万邻点。

**主要定理**

该问题可表述为在 $|V(G)|=n$、$\nu(G)=p$ 且添加任意缺失边均增大匹配数的条件下，最小化 $|E(G)|$。在第 3.1 节对最优值（即 $(p+1)K_2$-饱和图的最少边数）进行预备分析后，我们在第 3.2 节陈述并证明本文的主要定理——定理 4。

**定理 4 的推论**

定理 4 覆盖了 $n$ 的整个取值范围，因此解决了问题 1。我们已指出该定理推广了 Zhang、Lu 和 Yu 在 [9] 中的定理 3；当 $n\frac{1+\sqrt{2n+1}}{2}$$

时……

**结论**

在本文中，我们通过确定所有 $n\geq 2p+2$ 时的饱和数 $\mathrm{sat}(n,(p+1)K_2)$ 来解决问题 1，而不仅限于 $2p+2\leq n<3p$ 的范围。主要结果——定理 4 通过参数 $z$ 给出显式公式，并表明当 $n>2k^2-2k$ 时最优值在 $z\in\{\lfloor z^\dagger\rfloor,\lceil z^\dagger\rceil\}$ 处取得，而当 $n\leq 2k^2-2k$ 时 $z=0$（其中 $k=n-2p$）。对于有限个 $n\leq 18$ 的小情形，我们通过穷举枚举完成了分析。

在 $K_2$ 匹配情形之外，我们期望本文的结果将对……有用。

Xiaoteng Zhou | Kazuya Haraguchi | Hanchun Yuan