Let k ≥ 1 be an integer and G be a graph of minimum degree δ(G) ≥ k − 1. A set D ⊆ V(G) is said to be a k-tuple dominating set of G if |N[v] ∩ D| ≥ k for every vertex v ∈ V(G), where N[v] represents the closed neighbourhood of vertex v. The minimum cardinality among all k-tuple dominating sets is the k-tuple domination number of G. In this paper, we continue with the study of this classical domination parameter in graphs. In particular, we provide some relationships that exist between the k-tuple domination number and other classical parameters, like the multiple domination parameters, the independence number, the diameter, the order and the maximum degree. Also, we show some classes of graphs for which these relationships are achieved.
Keywords: $$-domination, $$-tuple domination, double domination
@article{RO_2022__56_5_3491_0,
author = {Martinez, Abel Cabrera},
title = {Some new results on the $k$-tuple domination number of graphs},
journal = {RAIRO. Operations Research},
pages = {3491--3497},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {5},
doi = {10.1051/ro/2022159},
mrnumber = {4497835},
zbl = {1502.05188},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2022159/}
}
TY - JOUR AU - Martinez, Abel Cabrera TI - Some new results on the $k$-tuple domination number of graphs JO - RAIRO. Operations Research PY - 2022 SP - 3491 EP - 3497 VL - 56 IS - 5 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2022159/ DO - 10.1051/ro/2022159 LA - en ID - RO_2022__56_5_3491_0 ER -
Martinez, Abel Cabrera. Some new results on the $k$-tuple domination number of graphs. RAIRO. Operations Research, Tome 56 (2022) no. 5, pp. 3491-3497. doi: 10.1051/ro/2022159
[1] , and , Topics in domination in graphs, in Developments in Mathematics. Springer (2020). | MR | Zbl
[2] and , -domination in graphs, in Graph theory with applications to algorithms and computer science. Wiley-Intersci. Publ., Wiley, New York (1985) 283–300. | MR | Zbl
[3] and , On -domination, -dependence and forbidden subgraphs, in Graph theory with applications to algorithms and computer science. Kalamazoo, Michigan (1984); Wiley-Intersci. Publ., Wiley, New York (1985) 301–311. | MR | Zbl
[4] and , Nordhaus-Gaddum inequalities for domination in graphs. Discrete Math. 155 (1996) 99–105. | MR | Zbl | DOI
[5] and , Double domination in graphs. Ars Combin. 55 (2000) 201–213. | MR | Zbl
[6] and , Multiple domination, in Topics in Domination in Graphs. Developments in Mathematics. Springer (2020) 151–203. | MR | Zbl | DOI
[7] , and , Upper bounds for -tuple (total) domination numbers of regular graphs. Bull. Iran. Math. Soc. 46 (2020) 573–577. | MR | Zbl | DOI
[8] , A note on the -tuple domination number of graphs. Ars Math. Contemp. 22 (2022) P4.03. | MR | Zbl | DOI
[9] and , Bipartite graphs with close domination and -domination numbers. Open Math. 18 (2020) 873–885. | MR | Zbl | DOI
[10] , Upper bounds on the -tuple domination number and -tuple total domination number of a graph. Australas. J. Comb. 73 (2019) 280–290. | MR | Zbl
[11] , , and , Solving the -dominating set problem on very large-scale networks. Comput. Soc. Netw. 7 (2020) 4. | DOI
[12] and ,-tuple domination in graphs. Inform. Process. Lett. 87 (2003) 45–50. | MR | Zbl | DOI
[13] , New bounds on the double domination number of trees. Discrete Appl. Math. 315 (2022) 97–103. | MR | Zbl | DOI
[14] and , A note on double domination in graphs. Discrete Appl. Math. 300 (2021) 107–111. | MR | Zbl | DOI
[15] , , and , On domination and annihilation in graphs with claw-free blocks. Discrete Math. 231 (2001) 143–151. | MR | Zbl | DOI
[16] and , Hardness results and approximation algorithms of -tuple domination in graphs. Inform. Process. Lett. 89 (2004) 75–83. | MR | Zbl | DOI
Cité par Sources :
