On the complexity of multiple bondage in graphs

Nader Jafari Rad

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=116829
Date :  2019/09/11
Publish in :    Theoretical Computer Science
DOI :  https://doi.org/10.1016/j.tcs.2019.09.008
Link :  http://dx.doi.org/10.1016/j.tcs.2019.09.008
Keywords :Multiple bondage- Np-hard,p-domination

Abstract :

---

Let p be a positive integer. The bondage number (p-bondage number, p-total bondage number, p-tuple bondage number, double bondage number) of a graph G, is the minimum number of edges whose removal from G results in a graph with larger domination number (respectively, p-domination number, p-total domination number, p-tuple domination number, double domination number). In this paper we show that the decision problems for these variants are NP-hard, even when restricted to bipartite graphs, thus improving the results on the complexity of multiple bondage given in J. Complexity 31(5), 754-761 (2015).