On the complexity of multiple bondage in graphs

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 N. Jafari Rad (2015) [14]. (C) 2019 Elsevier B.V. All rights reserved.