Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6416968 | Journal of Complexity | 2015 | 8 Pages |
Abstract
Let pâ¥2 be a positive integer. The p-bondage number of a graph G is the minimum number of edges whose removal from G results in a graph with larger p-domination number. The p-total bondage number of a graph G with no isolated vertex is the minimum number of non-pendant edges whose removal from G results in a graph with larger p-total domination number. The non-isolating p-bondage number of G is the minimum number of non-pendant edges whose removal from G results in a graph with larger p-domination number. In this paper we show that the decision problems for these multiple bondage problems are NP-hard.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Analysis
Authors
Nader Jafari Rad,