Independent Bondage Number in Graphs under Girth Constraints

Basic Information

• Paper ID: 2411.01687
• Title: Independent Bondage Number in Graphs under Girth Constraints
• Authors: E.G.K.M. Gamlath, Andrew Pham, Bing Wei
• Classification: math.CO (Combinatorics)
• Publication Date: October 15, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2411.01687

Abstract

Given a finite simple graph $G$, the independent bondage number of graph $G$ is the size of the minimum edge set whose deletion results in a graph with independent domination number strictly greater than that of $G$. While the bondage number of graphs under girth constraints has been studied, results for the independent bondage number remain scarce. This research establishes upper bounds for the independent bondage number of planar graphs under given girth constraints, extending results by Fischermann, Rautenbach, and Volkmann on bondage numbers and results by Borodin and Ivanova on planar graph structure. Specifically, additional structural properties are identified and bounds are established for planar graphs satisfying $\delta(G) \geq 2$ and $g(G) \geq 5$, $\delta(G) \geq 3$ and $g(G) \geq 4$, and $\delta(G) \geq 2$ and $g(G) \geq 10$.

Research Background and Motivation

Problem Definition and Significance

1. Core Concepts:
   • Independent dominating set: A vertex set that is both independent and dominating
   • Independent domination number $\gamma_i(G)$: The cardinality of a minimum independent dominating set
   • Independent bondage number $b_i(G)$: The size of the minimum edge set $B$ such that $\gamma_i(G-B) > \gamma_i(G)$
2. Research Significance:
   • Measures the vulnerability of network independent dominating structures under edge failures
   • Has important applications in link failure analysis of interconnection networks
   • Extends the scope of classical domination theory research
3. Limitations of Existing Research:
   • Traditional bondage number $b(G)$ has been systematically studied under girth constraints
   • Results on independent bondage number $b_i(G)$ are extremely limited, particularly under girth constraints
   • Lacks constant upper bound results for specific graph classes
4. Research Motivation:
   • Inspired by Fischermann et al. (2003) on girth-constrained bondage numbers of planar graphs
   • Naturally explores whether independent bondage number can also achieve similar constant upper bounds under girth constraints
   • Fills gaps in the theoretical study of independent bondage numbers

Core Contributions

1. Establishes four main constant upper bound theorems:
   • When $\delta(G) \geq 3$ and $g(G) \geq 4$: $b_i(G) \leq 6$
   • When $\delta(G) \geq 2$ and $g(G) \geq 5$: $b_i(G) \leq 5$
   • When $\delta(G) \geq 2$ and $g(G) \geq 7$: $b_i(G) \leq 4$
   • When $\delta(G) \geq 2$ and $g(G) \geq 10$: $b_i(G) \leq 3$
2. Identifies multiple critical graph structural configurations:
   • For $\delta(G) \geq 2$ and $g(G) \geq 5$: Identifies 10 unavoidable configurations
   • For $\delta(G) \geq 3$ and $g(G) \geq 4$: Identifies 3 critical configurations
   • Constructs corresponding independent bondage sets for each configuration
3. Extends existing theoretical frameworks:
   • Generalizes Fischermann et al.'s bondage number results to independent bondage numbers
   • Utilizes and develops Borodin and Ivanova's planar graph structure theory
4. Provides systematic proof methodology:
   • Employs the discharging method to identify unavoidable structures
   • Provides constructive proofs of independent bondage sets for each structure

Detailed Methodology

Theoretical Foundation

Definition System:

• Independent bondage number of graph $G$: $b_i(G) = \min\{|B| : B \subseteq E(G), \gamma_i(G-B) > \gamma_i(G)\}$
• Girth $g(G)$: The length of the shortest cycle in the graph
• Minimum degree $\delta(G)$: The minimum degree of vertices in the graph

Key Lemma:

Theorem 1 (Priddy, Wang, Wei): For any non-empty graph G,
b_i(G) ≤ min{d(u) + d(v) - |N(u) ∩ N(v)| - 1 : uv ∈ E(G)}

Core Method: Discharging Technique

Discharging Method Principles:

1. Initial Charge Assignment: Assign charges according to three natural approaches from Euler's formula
   • Vertex charge: $d(v) - 6$, face charge: $2\ell(f) - 6$ (vertex discharging)
   • Vertex charge: $2d(v) - 6$, face charge: $\ell(f) - 6$ (face discharging)
   • Vertex charge: $d(v) - 4$, face charge: $\ell(f) - 4$ (balanced discharging)
2. Charge Redistribution Rules: Design specific rules for charge flow from positively charged vertices/faces to negatively charged vertices/faces
3. Structure Identification: Prove the inevitability of certain structures through analysis of final charge distribution

Concrete Implementation Strategy

For the case $\delta(G) \geq 2$ and $g(G) \geq 5$:

Discharging Rules:

• (R1) Each 2-degree vertex receives $\frac{1}{2}$ charge from each adjacent vertex and each incident face
• (R2) Each 3-degree vertex receives $\frac{1}{3}$ charge from each incident face
• (R3) Charge assignment rules for specific 6-degree vertices
• (R4) Charge assignment rules for specific 5-degree vertices

Key Fact Verification:

• Fact 1: Each vertex of degree ≤ 4 has final charge 0
• Fact 2: Mutual exclusivity of charge assignments for 5+ degree vertices
• Facts 3-8: Non-negative charge guarantees for various vertices and faces

Main Results

Theorem 7: Structural Characterization for $\delta(G) \geq 2$ and $g(G) \geq 5$

Every planar graph $G$ satisfying the conditions must contain one of the following configurations:

• (a) $(2,4^-)$ edge or $(3,3^-)$ edge
• (b) Vertex $v \in S(5^+, [d(v)-1]^+)$ with remaining neighbors being 4-degree vertices or vertices in $S(5^+,1^+)$
• (c)-(j) Eight complex configurations involving 5-degree vertices and 2-degree neighbors sharing 5-faces

Theorem 8: Independent Bondage Number Upper Bound

For planar graphs $G$ with $\delta(G) \geq 2$ and $g(G) \geq 5$: $b_i(G) \leq 5$

Proof Strategy:

1. Construct edge sets $B$ of size ≤ 5 for each configuration
2. Prove that deletion of $B$ strictly increases the independent domination number
3. Use proof by contradiction and properties of independent dominating sets

Other Main Results

Theorem 10: $\delta(G) \geq 3$ and $g(G) \geq 4$ ⟹ $b_i(G) \leq 6$

Corollary 1: $\delta(G) \geq 2$ and $g(G) \geq 7$ ⟹ $b_i(G) \leq 4$ (based on Cranston-West lemma)

Theorem 13: $\delta(G) \geq 2$ and $g(G) \geq 10$ ⟹ $b_i(G) \leq 3$

Technical Innovations

Methodological Innovations

1. First systematic application of discharging method to independent bondage number research
2. Development of new charge assignment strategies: Designed specifically for the special properties of independent bondage numbers
3. Establishment of a complete framework linking structure identification and bondage set construction

Theoretical Contributions

1. Extension of classical results: Generalization from bondage number to independent bondage number
2. Filling theoretical gaps: Provides the first systematic results on independent bondage numbers under girth constraints
3. Identification of new graph structures: Discovers critical configurations affecting independent bondage numbers

Proof Techniques

1. Fine-grained charge analysis: Ensures correctness of the discharging process through detailed fact verification
2. Constructive proofs: Explicitly constructs independent bondage sets for each configuration
3. Completeness of case analysis: Exhaustively covers all possible structural configurations

Related Work

Historical Development

1. 1979: Garey and Johnson prove NP-completeness of the domination number problem
2. 1983: Bauer et al. introduce the concept of domination line stability
3. 1990: Fink et al. formally define bondage number
4. 2003: Fischermann et al. establish bondage number upper bounds under girth constraints

Independent Bondage Number Research

1. 2018: Priddy, Wang, Wei systematically study independent bondage numbers for the first time
2. 2021: Pham and Wei establish constant upper bounds for planar graphs with $\delta(G) \geq 3$
3. This paper: First study of independent bondage numbers under girth constraints

Technical Method Comparison

• Traditional methods: Primarily based on degree constraints and local structure analysis
• This paper's method: Combines girth constraints with discharging technique, providing finer structural characterization

Conclusions and Discussion

Main Conclusions

Establishes a complete system of upper bounds for independent bondage numbers of planar graphs under girth constraints: