2011/09/08 by Fu-Tao Hu, Hu, Fu-Tao, Jun-Ming Xu +1
Computer Science · Mathematics · #05C69 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #acm:05C69 #cs.CC #math.CO #msc:05C69
paper · pdf · doi:10.48550/arxiv.1109.1657
16 pages with 3 figures
arxiv created 2011/09/08 · arxiv updated 2011/09/09
Let G=(V,E) be a graph. A subset D⊆ V is a dominating set if every vertex not in D is adjacent to a vertex in D. A dominating set D is called a total dominating set if every vertex in D is adjacent to a vertex in D. The domination (resp. total domination) number of G is the smallest cardinality of a dominating (resp. total dominating) set of G. The bondage (resp. total bondage) number of a nonempty graph G is the smallest number of edges whose removal from G results in a graph with larger domination (resp. total domination) number of G. The reinforcement number of G is the smallest number of edges whose addition to G results in a graph with smaller domination number. This paper shows that the decision problems for bondage, total bondage and reinforcement are all NP-hard.