具有给定匹配数和覆盖数的图的最大规模

《Discrete Applied Mathematics》：Maximum size of a graph with given matching number and covering number

本文综述了对于给定顶点数n、匹配数k和覆盖数t（满足n ≥ 2k+1 且 k ≤ t ≤ 2k）的图，其可能达到的最大边数（规模）进行了精确的确定，并给出了达到该最大规模的极值图的完整刻画。此结果不仅推广并验证了图论中的Erd?s匹配猜想在特定参数下的情形（Corollary 1.4），也为理解图的匹配数（ν）与覆盖数（τ）这两个核心极值参数之间的约束关系提供了重要的理论工具。文中应用了经典的Tutte-Berge公式等工具，所得结论在图论和组合极值理论领域具有基础性意义。

　　

结果亮点

定理1.2

设n、k和t为三个整数，满足n ≥ 2k+1 且 k ≤ t ≤ 2k。令G为一个顶点数为n、匹配数ν(G) = k且覆盖数τ(G) = t的图。那么，该图的最大边数e(G)满足以下不等式：

e(G) ≤ max{ C(t, 2) + t(2k + 1 - t), C(t+1, 2) + (2k - t)(n - t - 1) }。

（其中C(x, 2)表示从x个元素中选取2个的组合数）。

而且，等式成立当且仅当满足以下条件之一：

(i) 当 n < 2t + 1 时， G = (K_t∨ K?_2k+1-t) ∪ K?_n-2k-1;

(ii) 当 n > 2t + 1 时， G = K_2k-t∨ (K_2t-2k+1∪ K?_n-t-1);

(iii) 当 n = 2t + 1 时， G是(i)或(ii)中描述的图。

需要注意的是，对于任意图G，如果其匹配数ν(G) = k，那么其覆盖数必然满足k ≤ τ(G) ≤ 2k。因此，定理1.2的结论是完备的。

为了表达简洁，我们用[n]来表示集合{1,2,...,n}，对于两个满足a < b的整数a和b，用[a,b]表示集合{a, a+1, ..., b}。在整篇文章中，[n]将作为具有n个顶点的超图的顶点集。

在文献[9]中，Frankl和Kupavskii提出了以下猜想。

猜想1.3[9]

令H是一个顶点数为n的r-一致超图（r-graph）。如果ν(H) = k 且 τ(H) > k，那么其边数e(H)不超过一个由特定超图族定义的边数的最大值（具体定义详见原文）。

最近，Guo等人在[11]中验证了当k=3且n足够大时猜想1.3成立。据我们所知，该猜想在一般情形下仍未解决。

应用定理1.2，通过简单计算我们首先得到以下结果，这证实了猜想1.3在r=2（即图）这一特殊情形下的正确性。

推论1.4

设n和k为两个整数，满足n ≥ 2k + 1。令G是一个顶点数为n、匹配数ν(G) = k且覆盖数τ(G) > k的图。那么其最大边数为：

e(G) ≤ max{ C(2k+1, 2), C(k+2, 2) + (k - 1)(n - k - 2) }。

等式成立当且仅当满足以下条件之一：

(i) 当 n < (5/2)k + 3 时， G = K_2k+1∪ K?_n-2k-1;

(ii) 当 n > (5/2)k + 3 时， G = K_k-1∨ (K₃∪ K?_n-k-2);

(iii) 当 n = (5/2)k + 3 时， G是(i)或(ii)中描述的图。

类似地，我们还得到了以下结果。

推论1.5

设n和k为两个整数，满足n ≥ 2k + 1。令G是一个顶点数为n、匹配数ν(G) = k且覆盖数τ(G) ≤ t的图。那么其最大边数为：

e(G) ≤ max{ C(t, 2) + t(2k + 1 - t), C(k, 2) + k(n - k) }。

等式成立当且仅当满足以下条件之一：

(i) 当 C(t, 2) + t(2k + 1 - t) > C(k, 2) + k(n - k) 时， G = (K_t∨ K?_2k+1-t) ∪ K?_n-2k-1;

(ii) 当 C(t, 2) + t(2k + 1 - t) < C(k, 2) + k(n - k) 时， G = K_k∨ K?_n-k;

(iii) 当 C(t, 2) + t(2k + 1 - t) = C(k, 2) + k(n - k) 时， G是(i)或(ii)中描述的图。

定理1.2将在接下来的章节中得到证明。

定理1.2的证明

我们将以Tutte–Berge公式这个已知结论开始我们的证明。

定理2.1[2]

令G是一个顶点数为n的图。那么其匹配数ν(G)满足：

ν(G) = (1/2) * ( n - max_S?V(G){ o(G-S) - |S| } )。

其中o(G-S)表示从图G中移除顶点集S后，所剩子图中奇连通分量的数量。

我们现在来证明定理1.2。

定理1.2的证明

令G是一个顶点数为n、匹配数ν(G)=k、覆盖数τ(G)=t且具有最大可能边数的图。因为n ≥ 2k+1，根据定理2.1，存在一个顶点子集S ? V(G)，使得o(G-S) - |S| = n - 2ν(G)。令C是图G的一个覆盖集，满足|C| = τ(G)。我们通过以下断言来完成证明。

断言1

（证明在后续未提供的正文中继续）