×

On the complexity of the bondage and reinforcement problems. (English) Zbl 1239.05138

Summary: Let \(G=(V,E)\) be a graph. A subset \(D\subseteq 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.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Cockayne, E. J.; Dawes, R. M.; Hedetniemi, S. T., Total domination in graphs, Networks, 10, 211-219 (1980) · Zbl 0447.05039
[2] Domke, G. S.; Hattingh, J. H.; Hedetniemi, S. T.; Laskar, R. C.; Markus, L. R., Restrained domination in graphs, Discrete Math., 203, 61-69 (1999) · Zbl 1114.05303
[3] Fink, J. F.; Jacobson, M. S.; Kinch, L. F.; Roberts, J., The bondage number of a graph, Discrete Math., 86, 47-57 (1990) · Zbl 0745.05056
[4] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[5] Henning, M. A., A survey of selected recent results on total domination in graphs, Discrete Math., 309, 1, 32-63 (2009) · Zbl 1219.05121
[6] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0890.05002
[7] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Domination in Graphs: Advanced Topics (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0883.00011
[8] Henning, M. A.; Rad, N. J.; Raczek, J., A note on total reinforcement in graphs, Discrete Appl. Math., 159, 14, 1443-1446 (2011) · Zbl 1231.05203
[9] Hartnell, B. L.; Jorgensen, L. K.; Vestergaard, P. D.; Whitehead, C., Edge stability of the \(k\)-domination number of trees, Bulletin of the ICA, 22, 31-40 (1998) · Zbl 0890.05036
[10] Hattingh, J. H.; Plummer, A. R., Restrained bondage in graphs, Discrete Math., 308, 5446-5453 (2008) · Zbl 1186.05091
[11] Huang, J.; Xu, J.-M., The total domination and bondage numbers of extended de bruijn and Kautz digraphs, Comput. Math. Appl., 53, 8, 1206-1213 (2007) · Zbl 1130.05044
[12] Huang, J.; Wang, J.-W.; Xu, J.-M., Reinforcement numbers of digraphs, Discrete Appl. Math., 157, 8, 1938-1946 (2009) · Zbl 1204.05068
[13] Kok, J.; Mynhardt, C. M., Reinforcement in graphs, Congr. Numer, 79, 225-231 (1990) · Zbl 0862.05071
[14] Kulli, V. R.; Patwari, D. K., The total bondage number of a graph, (Kulli, V. R., Advances in Graph Theory (1991), Vishwa: Vishwa Gulbarga), 227-235 · Zbl 0785.05055
[15] Laskar, R. C.; Pfaff, J.; Hedetniemi, S. M.; Hedetniemi, S. R., On the algorithmic complexity of total domination, SIAM J. Algebraic Discrete Methods, 5, 420-425 (1984) · Zbl 0576.68056
[16] Sridharan, N.; Elias, M. D.; Subramanian, V. S.A., Total bondage number of a graph, AKCE Int. J. Graphs Comb., 4, 2, 203-209 (2007) · Zbl 1135.05056
[17] Sridharan, N.; Elias, M. D.; Subramanian, V. S.A., Total reinforcement number of a graph, AKCE Int. J. Graphs Comb., 4, 2, 197-202 (2007) · Zbl 1136.05052
[18] Telle, J. A.; Proskurowski, A., Algorithms for vertex partitioning problems on partial \(k\)-trees, SIAM J. Discrete Math., 10, 529-550 (1997) · Zbl 0885.68118
[19] Xu, J.-M., Theory and Application of Graphs (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, Boston, London
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.