The Algorithmic Complexity of Bondage and Reinforcement Problems in bipartite graphs
Preprint
Abstract
Let $G=(V,E)$ be a graph. A subset $D\subseteq V$ is a dominating set if every vertex not in $D$ is adjacent to a vertex in $D$. The domination number of $G$, denoted by $\gamma(G)$, is the smallest cardinality of a dominating set of $G$. The bondage number of a nonempty graph $G$ is the smallest number of edges whose removal from $G$ results in a graph with domination number larger than $\gamma(G)$. The reinforcement number of $G$ is the smallest number of edges whose addition to $G$ results in a graph with smaller domination number than $\gamma(G)$. In 2012, Hu and Xu proved that the decision problems for the bondage, the total bondage, the reinforcement and the total reinforcement numbers are all NP-hard in general graphs. In this paper, we improve these results to bipartite graphs.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- On Bondage Numbers of Graphs: A Survey with Some CommentsInternational Journal of Combinatorics, 2013
- On the complexity of the bondage and reinforcement problemsJournal of Complexity, 2012
- A note on total reinforcement in graphsDiscrete Applied Mathematics, 2011
- Reinforcement numbers of digraphsDiscrete Applied Mathematics, 2009
- A survey of selected recent results on total domination in graphsDiscrete Mathematics, 2009
- Restrained bondage in graphsDiscrete Mathematics, 2008
- The total domination and total bondage numbers of extended de Bruijn and Kautz digraphsComputers & Mathematics with Applications, 2007
- The bondage number of a graphDiscrete Mathematics, 1990
- The NP-completeness of steiner tree and dominating set for chordal bipartite graphsTheoretical Computer Science, 1987