图的平衡扩张中的脆弱性参数

《Discrete Applied Mathematics》：Vulnerability parameters in balanced blow-ups of graphs

　　

• 提供了一种通用的方法，用于计算平衡膨胀图 G(m) 的脆弱性参数，该方法基于 G 的参数，此前一直缺乏此类方法。
• 技术贡献：关键引理和定理（例如定理 4.3、引理 5.1）证明充分，是本文核心贡献。
• 应用：扩展了 Mamut–Vumar 和 Paulraja–Agnes 的研究成果。
• 关注 K?nig–Egerváry 图：脆弱性与匹配/独立结构之间的关联。

## 引言

图的脆弱性度量用于量化网络在节点或边故障下的抗灾能力，在通信网络、分布式系统和组合优化问题的分析中发挥着核心作用。经典的脆弱性参数，如点连通度、韧性、散射数、十韧度、断裂度和完整性，从互补的角度刻画了图在移除节点后碎片化的方式。过去几十年来，这些概念从结构和算法两个角度得到了广泛研究，这与哈密顿性、匹配理论和网络可靠性之间存在密切的联系。

文献中一个反复出现的主题是脆弱性参数在图操作下的表现。特别是，图积和图替换常被用作从小构件构建大型网络的模型。在这些操作中，图的膨胀占据核心地位。给定一个图 G 和一个正整数 m，平衡膨胀 G(m) 将 G 的每个顶点替换为大小为 m 的独立集，将每条边替换为对应顶点集之间的完全二部图。平衡膨胀在 Kronecker（直积）图积、有限环上的 Cayley 图以及网络设计中各种复制过程的研究中自然出现。

本文的主要目的是研究多个经典脆弱性参数在有限简单图的平衡膨胀下的表现。我们的方法基于对 G(m) 中点割的详细分析，以及点割与原图 G 的点割之间的关系。我们证明，对于优化本文中考虑的所有脆弱性参数，只需关注 G(m) 中由 G 的点割对应的完整纤维组成的点割。这一观察结果得出了显式公式，将 G(m) 的脆弱性参数完全用 G 的结构性质来表示。

在我们的分析中，接受最大独立集的补集作为最优点割的图起着核心作用。这促使我们引入了"最优 MIS 割"的概念。我们证明，当 G 接受最优 MIS 割时，其平衡膨胀的脆弱性参数会大大简化。特别地，对于 K?nig–Egerváry 图（满足 α(G)+μ(G)=|G|），我们的公式揭示了脆弱性参数与匹配和独立集之间平衡的紧密联系。因此，我们得到了大量图族及其平衡膨胀的韧性、十韧度、散射数、断裂度和完整性的闭式表达式。

本文组织如下。第 2 节回顾了一些定义和脆弱性参数的基本性质。第 3 节分析平衡膨胀中的点割并建立关键的提升结果。第 4–7 节分别计算平衡膨胀的点连通度、韧性、十韧度、散射数、断裂度和完整性。第 8 节聚焦于 K?nig–Egerváry 图及相关图类。最后，第 9 节将我们的结果应用于完全图和完全均衡图的 Kronecker 积。

## 预备知识

本文讨论的所有图均为有限、无向、简单图。对于未定义的术语或符号，请参阅 [31] 或 [13]。

设 G=(V,E) 为一个图。我们将边 e={u,v} 简记为 uv。对于 e∈E(G) 和 v∈V(G)，我们定义 G?e?(V,E?{e}) 和 G?v?(V?{v},{uw∈E:u,w≠v})。若 X?V(G)，G 中由 X 诱导的子图记为 G[X]。

图的阶（顶点数）记为 |G| 或 |V(G)|，在不引起歧义时使用。v 的邻域记为 NG(v)={u∈V(G):vu∈E(G)}。

## 点割和图的平衡膨胀

我们引入一些符号。对于图 G，S?V(G) 和 m∈?，我们定义 G(m) 的以下顶点集合 S(m)={(v,i):v∈S, i=1,…,m}。

类似地，给定 R?V(G(m))，我们定义 G 的以下顶点集合 Rm={v∈V(G):(v,i)∈R, ?i=1,…,m}。

**引理 3.1** 设 G 为连通图，m∈?。设 S 和 R 分别为 G 和 G(m) 的顶点子集。则：
(a) 若 S 是 G 的点割，则 S(m) 是 G(m) 的点割。
(b) 若 R 是 G(m) 的点割，则 Rm 是 G 的点割。

**证明** 对于 (a)，只需注意到……

## 平衡膨胀图中的最优割

本文出现的多个最优割具有一个显著的结构特征：它们恰好是最大独立集的补集。受此经验观察的启发，我们引入以下概念。

给定图 G 及其最大独立集 S。若集合 R?V(G)?S 是 G 的韧性的最优点割，即 τ(G)=|R|/c(G?R)=(|G|?α(G))/α(G)，则称 G 接受最优 MIS 割。

本节中，我们看到 MIS 最优条件对……

## 膨胀图的韧性和十韧度

本节研究图的平衡膨胀的韧性和十韧度。

作为定理 3.4 和引理 4.1 的直接推论，我们得到以下结果，该结果允许我们利用 G 的点割来计算 G(m) 的韧性。

**定理 5.1** 设 G 为连通图，m∈?。则 τ(G(m))=min{m|S|/((m?1)i(G?S)+c(G?S))}，其中最小值取遍 G 的所有点割 S。

**证明** 由定理 3.4，存在 G 的一个点割 S，使得 τ(G(m))=|S(m)|/c(G(m)?S(m))。因此，引理 4.1 蕴含 τ(S……

## 膨胀图的散射数和断裂度

本节研究图的平衡膨胀的散射数和断裂度。

我们从以下有用结果开始，该结果允许我们用 G 的点割来表达膨胀 G(m) 的散射数。

**引理 6.1** 设 G 为图，S 为 G 的最大独立集，R=V(G)?S。若 W 是 G 的点割且 |W|≥|R|，则 c(G?W)?|W|≤c(G?R)?|R|。

**证明** 设 C?,…,C? 和 D?,…,D? 分别为 G?W 和 G?R 的连通分量。显然，t=c(G?W)，r=c(G?R)=|S|=α(G)，且 |D?|=……

## 膨胀图的完整性

本节研究平衡膨胀的完整性参数。

**命题 7.1** 设 G 为连通图，m∈?，R?V(G(m)) 满足 c(G(m)?R)>1。则 |R|+ω(G(m)?R)≥|R?|+ω(G(m)?R?)。

**证明** 若 R?=R，则无需证明。否则，令 x=(v,i)∈R?R?，设 R′=R?{x}。由引理 3.2，当 x 被恢复时，它要么成为孤立点，要么被加入到已有的连通分量中。在第一种情况下，ω(G(m)?R′)=ω(G(m)?R)；在第二种情况下，ω(G(m)?R′)≤ω(G(m)?R)+1。由于 |R′|=|R|?1，……

## K?nig–Egerváry 图中的最优 MIS 割

对于 K?nig–Egerváry 图，我们有 |G|?α(G)=μ(G)，因此任何最优 MIS 韧性值简化为 τ(G)=μ(G)/α(G)。这表明此类图的脆弱性可以直接用独立和匹配之间的平衡来解释。

设 C∪I 为分裂图的顶点划分，其中 C 是团，I 是独立集，且 C 中每个顶点与 I 中每个顶点相邻，参见 [14] 或 [18]。

**引理 8.1** 若 G 是具有顶点划分 C∪I 的分裂图，且……

## Kw(e)?Kz(d) 的脆弱性参数

本节利用前述结果以及 Mamut 和 Vumar 在 [32] 中获得的 Kw?Kz 的脆弱性参数，以更简洁的方式重新获得 Paulraja 和 Sheeran 在 [34] 中的结果，并补充计算了此前未计算的 Kw(e)?Kz(d) 的断裂度。

我们从以下有用引理开始，该引理断言图 Kw(e)?Kz(d) 是图 Kw?Kz 的膨胀。这里 Kw(e) 表示完全图 Kw 的 e-平衡膨胀，即……

## 生成式 AI 和 AI 辅助技术在写作过程中的声明

在本工作的准备过程中，作者使用了 ChatGPT-3.5 以改进文本若干段落的语法。使用该服务后，作者根据需要审核和编辑了内容，并对出版物的内容承担全部责任。

## 利益冲突声明

作者声明不存在可能影响本文报告工作的已知竞争性经济利益或个人关系。

## 致谢

本工作部分由阿根廷国立圣路易斯大学（Universidad Nacional de San Luis）资助，PI UNSL 03-1326，I+D+i 基金会，PICT-2020-Serie A-00549 项目，以及 CONICET 资助项目 PIP 11220220100068CO。

Denis E. Videla | Daniel A. Jaume | Kevin Pereyra