2025-11-23T04:19:16.663058

Independent Bondage Number in Graphs under Girth Constraints

Gamlath, Pham, Wei

Given a finite, simple graph $G$, the independent bondage number of $G$ is the minimum size of an edge set such that its deletion results in a graph with strictly larger independent domination number than that of $G$. While the bondage number of graphs under girth constraints has been studied, very few results have yet been established for the independent bondage number. In this study, we establish upper bounds on the independent bondage number of planar graphs under given girth constraints, extending results on the bondage number by Fischermann, Rautenbach, and Volkmann and on the structures of planar graphs by Borodin and Ivanova. In particular, we identify additional structures and establish bounds on the independent bondage number for planar graphs with $Î´(G) \geq 2$ and $g(G)\geq 5$, $Î´(G)\geq 3$ and $g(G)\geq 4$, and $Î´(G) \geq 2$ and $g(G)\geq 10$.

academic

Independent Bondage Number in Graphs under Girth Constraints

基本信息

论文ID: 2411.01687
标题: Independent Bondage Number in Graphs under Girth Constraints
作者: E.G.K.M. Gamlath, Andrew Pham, Bing Wei
分类: math.CO (组合数学)
发表时间: October 15, 2025 (arXiv预印本)
论文链接: https://arxiv.org/abs/2411.01687

摘要

给定有限简单图 $G$ ，图 $G$ 的独立束缚数(independent bondage number)是使得删除后得到的图具有严格大于 $G$ 的独立支配数的最小边集的大小。虽然在周长约束下的图的束缚数已被研究，但对于独立束缚数的结果仍然很少。本研究在给定周长约束下建立了平面图独立束缚数的上界，扩展了Fischermann、Rautenbach和Volkmann关于束缚数的结果以及Borodin和Ivanova关于平面图结构的结果。特别地，识别了额外的结构并建立了满足 $\delta(G) \geq 2$ 且 $g(G) \geq 5$ 、 $\delta(G) \geq 3$ 且 $g(G) \geq 4$ 、以及 $\delta(G) \geq 2$ 且 $g(G) \geq 10$ 的平面图独立束缚数的界。

研究背景与动机

问题定义与重要性

核心概念：
- 独立支配集：既是独立集又是支配集的顶点集合
- 独立支配数 $\gamma_i(G)$ ：最小独立支配集的基数
- 独立束缚数 $b_i(G)$ ：使得 $\gamma_i(G-B) > \gamma_i(G)$ 的最小边集 $B$ 的大小
研究意义：
- 衡量网络在边失效情况下独立支配结构的脆弱性
- 在互连网络的链路故障分析中具有重要应用价值
- 扩展了经典支配理论的研究范围
现有研究局限：
- 传统束缚数 $b(G)$ 在周长约束下已有系统研究
- 独立束缚数 $b_i(G)$ 相关结果极为有限，特别是在周长约束条件下
- 缺乏针对特定图类的常数上界结果
研究动机：
- 受Fischermann等人(2003)关于平面图束缚数周长约束结果的启发
- 自然地探索独立束缚数是否也能在周长约束下获得类似的常数上界
- 填补独立束缚数理论研究的空白

核心贡献

建立了四个主要的常数上界定理：
- $\delta(G) \geq 3$ 且 $g(G) \geq 4$ 时： $b_i(G) \leq 6$
- $\delta(G) \geq 2$ 且 $g(G) \geq 5$ 时： $b_i(G) \leq 5$
- $\delta(G) \geq 2$ 且 $g(G) \geq 7$ 时： $b_i(G) \leq 4$
- $\delta(G) \geq 2$ 且 $g(G) \geq 10$ 时： $b_i(G) \leq 3$
识别了多种关键图结构配置：
- 对于 $\delta(G) \geq 2$ 且 $g(G) \geq 5$ ：识别了10种不可避免的配置
- 对于 $\delta(G) \geq 3$ 且 $g(G) \geq 4$ ：识别了3种关键配置
- 为每种配置构造了相应的独立束缚集
扩展了现有理论框架：
- 推广了Fischermann等人的束缚数结果到独立束缚数
- 利用并发展了Borodin和Ivanova的平面图结构理论
提供了系统的证明方法：
- 采用放电方法(discharging method)识别不可避免结构
- 为每种结构提供了构造性的独立束缚集证明

方法详解

理论基础

定义体系：

图 $G$ 的独立束缚数： $b_i(G) = \min\{|B| : B \subseteq E(G), \gamma_i(G-B) > \gamma_i(G)\}$
周长 $g(G)$ ：图中最短圈的长度
最小度 $\delta(G)$ ：图中顶点的最小度数

关键引理：

定理1 (Priddy, Wang, Wei): 对于非空图G，
b_i(G) ≤ min{d(u) + d(v) - |N(u) ∩ N(v)| - 1 : uv ∈ E(G)}

核心方法：放电技术

放电方法原理：

初始电荷分配：根据Euler公式的三种自然方式分配电荷
- 顶点电荷： $d(v) - 6$ ，面电荷： $2\ell(f) - 6$ (顶点放电)
- 顶点电荷： $2d(v) - 6$ ，面电荷： $\ell(f) - 6$ (面放电)
- 顶点电荷： $d(v) - 4$ ，面电荷： $\ell(f) - 4$ (平衡放电)
电荷重分配规则：设计特定规则使电荷从正电荷顶点/面流向负电荷顶点/面
结构识别：通过分析最终电荷分布，证明某些结构的不可避免性

具体实现策略

对于 $\delta(G) \geq 2$ 且 $g(G) \geq 5$ 的情况：

放电规则：

(R1) 每个2度顶点从每个相邻顶点和每个关联面各取 $\frac{1}{2}$ 电荷
(R2) 每个3度顶点从每个关联面取 $\frac{1}{3}$ 电荷
(R3) 特定6度顶点的电荷分配规则
(R4) 特定5度顶点的电荷分配规则

关键事实验证：

事实1：每个度数≤4的顶点最终电荷为0
事实2：5+度顶点的电荷分配互斥性
事实3-8：各种顶点和面的非负电荷保证

主要结果

定理7： $\delta(G) \geq 2$ 且 $g(G) \geq 5$ 的结构刻画

每个满足条件的平面图 $G$ 必包含以下配置之一：

(a) $(2,4^-)$ 边或 $(3,3^-)$ 边
(b) 顶点 $v \in S(5^+, [d(v)-1]^+)$ 且其余邻居为4-度顶点或 $S(5^+,1^+)$ 中的顶点
(c)-(j) 八种涉及5度顶点与2度邻居共享5-面的复杂配置

定理8：独立束缚数上界

对于 $\delta(G) \geq 2$ 且 $g(G) \geq 5$ 的平面图 $G$ ： $b_i(G) \leq 5$

证明思路：

对每种配置构造大小≤5的边集 $B$
证明删除 $B$ 后独立支配数严格增加
使用反证法和独立支配集的性质

其他主要结果

定理10： $\delta(G) \geq 3$ 且 $g(G) \geq 4$ ⟹ $b_i(G) \leq 6$

推论1： $\delta(G) \geq 2$ 且 $g(G) \geq 7$ ⟹ $b_i(G) \leq 4$ (基于Cranston-West引理)

定理13： $\delta(G) \geq 2$ 且 $g(G) \geq 10$ ⟹ $b_i(G) \leq 3$

技术创新点

方法论创新

首次将放电方法系统应用于独立束缚数研究
发展了新的电荷分配策略：针对独立束缚数的特殊性质设计
建立了结构识别与束缚集构造的完整框架

理论贡献

扩展了经典结果：从束缚数推广到独立束缚数
填补了理论空白：提供了周长约束下独立束缚数的首批系统结果
识别了新的图结构：发现了影响独立束缚数的关键配置

证明技巧

精细的电荷分析：通过详细的事实验证确保放电过程的正确性
构造性证明：为每种配置明确构造独立束缚集
案例分析的完整性：穷尽所有可能的结构配置

结论与讨论

主要结论

建立了平面图独立束缚数在周长约束下的完整上界体系： $b_i(G) \leq \begin{cases} 6, & \text{if } g(G) \geq 4 \text{ and } \delta(G) \geq 3 \\ 5, & \text{if } g(G) \geq 5 \text{ and } \delta(G) \geq 2 \\ 4, & \text{if } g(G) \geq 7 \text{ and } \delta(G) \geq 2 \\ 3, & \text{if } g(G) \geq 10 \text{ and } \delta(G) \geq 2 \end{cases}$