×

On the global total \(k\)-domination number of graphs. (English) Zbl 1414.05216

Summary: A subset \(D\) of vertices of a graph \(G\) is a global total \(k\)-dominating set if \(D\) is a total \(k\)-dominating set of both \(G\) and \(\overline{G}\). The global total \(k\)-domination number of \(G\) is the minimum cardinality of a global total \(k\)-dominating set of \(G\) and it is denoted by \(\gamma_{k t}^g(G)\). In this paper we introduce this concept and we begin the study of its mathematical properties. Specifically, we prove that the complexity of the decision problem associated to the computation of the value \(\gamma_{k t}^g(G)\) is NP-complete. Moreover, we present tight bounds for this parameter and we obtain relationships between the global total \(k\)-domination number of \(G\) and the total \(k\)-domination numbers of \(G\) and \(\overline{G}\), and other parameters of the graph \(G\).

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.)
Full Text: DOI

References:

[1] Akhbari, M. H.; Eslahchiz, C.; Jafari Rad, N.; Hasni, R., Some Remarks on Global Total Domination in Graphs, Appl. Math. E-Notes, 15, 22-28 (2015) · Zbl 1333.05212
[2] 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
[3] Bermudo, S.; Jalemskaya, D. L.; Sigarreta, J. M., Total 2-domination in Grid graphs, Util. Math. (2017), (in press)
[4] Bermudo, S.; Sánchez, J. L.; Sigarreta, J. M., Total \(k\)-domination in Cartesian product graphs, Period. Math. Hungar., 75, 255-267 (2017) · Zbl 1413.05279
[5] Fernau, H.; Rodríguez-Velázquez, J. A.; Sigarreta, J. M., Global powerful r-alliances and total k-domination in graphs, Util. Math., 98, 127-147 (2015) · Zbl 1343.05115
[6] J. He, H. Liang, Complexity of Total k-Domination and Related Problems, Joint Conference of FAW 2011(the 5th International Frontiers of Algorithmics Workshop) and AAIM 2011 (the 7th International Conference on Algorithmic Aspects of Information and Management) 2011, pp. 147-155.; J. He, H. Liang, Complexity of Total k-Domination and Related Problems, Joint Conference of FAW 2011(the 5th International Frontiers of Algorithmics Workshop) and AAIM 2011 (the 7th International Conference on Algorithmic Aspects of Information and Management) 2011, pp. 147-155. · Zbl 1329.68141
[7] Kulli, V. R., On n-total domination number in graphs, (Graph Theory, Combinatorics, Algorithms and Applications (1991), SIAM: SIAM Philadelphia), 319-324 · Zbl 0758.05083
[8] Kulli, V. R.; Janakiram, B., The total global domination number of a graph, Indian J. Pure. Appl. Math., 27, 537-542 (1996) · Zbl 0853.05050
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.