2021/07/23 by Valentin Bouquet, Bouquet, Valentin
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2107.11216
openalex publication_date 2021/07/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A set S⊆ V(G) of a graph G is a dominating set if each vertex has a neighbor in S or belongs to S. Let γ(G) be the cardinality of a minimum dominating set in G. The bondage number b(G) of a graph G is the smallest cardinality of a set of edges A⊆ E(G), such that γ(G-A)=γ(G)+1. The d-Bondage is the problem of deciding, given a graph G and an integer d≥ 1, if b(G)≤ d. This problem is known to be NP-hard even for bipartite graphs and d=1. In this paper, we show that 1-Bondage is NP-hard, even for the class of 3-regular planar graphs, the class of subcubic claw-free graphs, and the class of bipartite planar graphs of maximum degree 3, with girth k, for any fixed k≥ 3. On the positive side, for any planar graph G of girth at least 8, we show that we can find, in polynomial time, a set of three edges A such that γ(G-A)>γ(G). Last, we exposed some classes of graphs for which Dominating Set can be solved in polynomial time, and where d-Bondage can also be solved in polynomial time, for any fixed d≥ 1.