×

Algorithm and hardness results on neighborhood total domination in graphs. (English) Zbl 1458.05197

A set \(D \subseteq V\) is a dominating set in a graph \(G=(V,E)\) if \(\bigcup_{v \in D} N[v] = V\). The set \(D\) is total dominating if \(\bigcup_{v \in D} N(v) = V\). That is, the dominating set \(D\) is total dominating if \(G[D]\) has no isolated vertex. Finally, the dominating set \(D\) is neighbourhood total dominating if \(G[\bigcup_{v \in D} N(v)]\) has no isolated vertex. Every total dominating set is neighbourhood total dominating, and every neighbourhood total dominating set is dominating. Some complexity results on finding minimum neighbourhood total dominating sets are carried over from analogous results on minimum dominating sets.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Arumugam, S.; Sivagnanam, C., Neighborhood total domination in graphs, Opusc. Math., 31, 519-531 (2011) · Zbl 1230.05223
[2] Ausiello, G.; Protasi, M.; Marchetti-Spaccamela, A.; Gambosi, G.; Crescenzi, P.; Kann, V., Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties (1999), Springer-Verlag: Springer-Verlag New York · Zbl 0937.68002
[3] Bermudo, S.; Hernández-Gómez, J. C.; Sigarreta, J. M., On the total k-domination in graphs, Discuss. Math., Graph Theory, 38, 301-317 (2018) · Zbl 1377.05137
[4] Bermudo, S.; Hernández-Gómez, J. C.; Sigarreta, J. M., Total k-domination in strong product graphs, Discrete Appl. Math., 263, 51-58 (2019) · Zbl 1414.05217
[5] Booth, K. S.; Johnson, J. H., Dominating sets in chordal graphs, SIAM J. Comput., 11, 191-199 (1982) · Zbl 0485.05055
[6] Chiarelli, N.; Hartinger, T. R.; Leoni, V. A.; Pujato, M. I.L.; Milanic, M., New algorithms for weighted k-domination and total k-domination problems in proper interval graphs, Theor. Comput. Sci., 795, 128-141 (2019) · Zbl 1434.68354
[7] Chlebík, M.; Chlebíková, J., Approximation hardness of dominating set problems in bounded degree graphs, Inf. Comput., 206, 1264-1275 (2008) · Zbl 1169.68037
[8] Chvátal, V., A greedy heuristic for the set-covering problem, Math. Oper. Res., 4, 233-235 (1979) · Zbl 0443.90066
[9] Davila, R.; Henning, M. A., Total forcing versus total domination in cubic graphs, Appl. Math. Comput., 354, 385-395 (2019) · Zbl 1428.05230
[10] Feige, U., A threshold of \(\ln n\) for approximating set cover, J. ACM, 45, 634-652 (1998) · Zbl 1065.68573
[11] Garey, M. R.; Johnson, D. S., Computers and Intractability; A Guide to the Theory of NP-Completeness (1990), W. H. Freeman & Co.: W. H. Freeman & Co. New York
[12] Goddard, W.; Henning, M. A., A note on domination and total domination in prisms, J. Comb. Optim., 35, 14-20 (2018) · Zbl 1434.05108
[13] Haynes, T. W.; Hedetniemi, S.; Slater, P., Domination in Graphs: Advanced Topics, Chapman & Hall/CRC Pure and Applied Mathematics (1998), Taylor & Francis · Zbl 0883.00011
[14] Haynes, T. W.; Hedetniemi, S.; Slater, P., Fundamentals of Domination in Graphs, Chapman & Hall/CRC Pure and Applied Mathematics (1998), Taylor & Francis · Zbl 0890.05002
[15] Henning, M. A., Recent results on total domination in graphs: a survey, Discrete Math., 309, 32-63 (2009) · Zbl 1219.05121
[16] Henning, M. A.; Rad, N. J., Bounds on neighborhood total domination in graphs, Discrete Appl. Math., 161, 2460-2466 (2013) · Zbl 1285.05139
[17] Henning, M. A.; Wash, K., Trees with large neighborhood total domination number, Discrete Appl. Math., 187, 96-102 (2015) · Zbl 1315.05100
[18] Henning, M. A.; Yeo, A., Total Domination in Graphs, Springer Monographs in Mathematics (2013), Springer-Verlag: Springer-Verlag New York · Zbl 1408.05002
[19] Jamision, R. E.; Laskar, R., Elimination orderings of chordal graphs, (Combinatorics and Applications. Combinatorics and Applications, Calcutta (1982/1984)), 192-200 · Zbl 0703.05049
[20] Lu, C.; Wang, B.; Wang, K., Algorithm complexity of neighborhood total domination and \(( \rho, \gamma_{\operatorname{nt}} )\)-graphs, J. Comb. Optim., 35, 424-435 (2018) · Zbl 1386.05137
[21] Ma, Y.; Cai, Q.; Yao, S., Integer linear programming models for the weighted total domination problem, Appl. Math. Comput., 358, 146-150 (2019) · Zbl 1428.90102
[22] Mojdeh, D. A.; Sayed Salehi, M. R.; Chellali, M., Neighborhood total domination of a graph and its complement, Australas. J. Comb., 65, 37-44 (2016) · Zbl 1344.05109
[23] Müller, H.; Brandstädt, A., The NP-completeness of steiner tree and dominating set for chordal bipartite graphs, Theor. Comput. Sci., 53, 257-265 (1987) · Zbl 0638.68062
[24] Panda, B. S.; Das, S. K., A linear time recognition algorithm for proper interval graphs, Inf. Process. Lett., 87, 153-161 (2003) · Zbl 1161.68855
[25] Papadimitriou, C. H.; Yannakakis, M., Optimization, approximation, and complexity classes, J. Comput. Syst. Sci., 43, 425-440 (1991) · Zbl 0765.68036
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.