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

グラフの周長制約下における独立結合数

基本情報

論文ID: 2411.01687
タイトル: Independent Bondage Number in Graphs under Girth Constraints
著者: E.G.K.M. Gamlath, Andrew Pham, Bing Wei
分類: math.CO (組合数学)
発表日: 2025年10月15日 (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)による平面グラフの結合数周長制約結果に着想を得た
- 独立結合数も周長制約下で同様の定数上界を得られるかどうかを自然に探究
- 独立結合数理論研究の空白を埋める

核心的貢献

4つの主要な定数上界定理を確立：
- $\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のグラフLaplacian理論を利用・発展
体系的な証明方法を提供：
- 放電法(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公式の3つの自然な方法に従って電荷を配分
- 頂点電荷： $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種類の複雑な配置

定理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}$