کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6416980 | 1338387 | 2012 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On the complexity of the bondage and reinforcement problems On the complexity of the bondage and reinforcement problems](/preview/png/6416980.png)
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 (resp. total reinforcement) number of G is the smallest number of edges whose addition to G results in a graph with smaller domination (resp. total domination) number. This paper shows that the decision problems for the bondage, total bondage, reinforcement and total reinforcement numbers are all NP-hard.
⺠The bondage for measuring the vulnerability of the network domination under link failure. ⺠The reinforcement for measuring the stability of the network domination under link addition. ⺠We show that the decision problems for the bondage and the reinforcement are NP-hard.
Journal: Journal of Complexity - Volume 28, Issue 2, April 2012, Pages 192-201