The complexity of the bondage problem in planar graphs

MaRDI QIDQ6373583zbMATH OpenFDO

Authors Valentin Bouquet

Publication date 23 July 2021

Abstract: A set $SsubseteqV(G)$ of a graph $G$ is a dominating set if each vertex has a neighbor in $S$ or belongs to $S$. Let $gamma(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 $AsubseteqE(G)$, such that $gamma(G-A)=gamma(G)+1$. The $d$-Bondage is the problem of deciding, given a graph $G$ and an integer $dgeq1$, if $b(G)leqd$. This problem is known to be $mathsfNP$-hard even for bipartite graphs and $d=1$. In this paper, we show that $1$-Bondage is $mathsfNP$-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 $kgeq3$. 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 $gamma(G-A)>gamma(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 $dgeq1$.

This page was built for publication: The complexity of the bondage problem in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6373583)