Geodesic
Total Domination in Generalized Prisms and a New Domination Invariant
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1165-1178.

Voir la notice de l'article provenant de la source Library of Science

In this paper we complement recent studies on the total domination of prisms by considering generalized prisms, i.e., Cartesian products of an arbitrary graph and a complete graph. By introducing a new domination invariant on a graph G, called the k-rainbow total domination number and denoted by γkrt(G), it is shown that the problem of finding the total domination number of a generalized prism G □ Kk is equivalent to an optimization problem of assigning subsets of 1, 2, . . ., k to vertices of G. Various properties of the new domination invariant are presented, including, inter alia, that γkrt(G) = n for a nontrivial graph G of order n as soon as k ≥ 2Δ(G). To prove the mentioned result as well as the closed formulas for the k-rainbow total domination number of paths and cycles for every k, a new weight-redistribution method is introduced, which serves as an efficient tool for establishing a lower bound for a domination invariant.
Keywords: domination, k -rainbow total domination, total domination 
@article{DMGT_2021_41_4_a19,
     author = {Tepeh, Aleksandra},
     title = {Total {Domination} in {Generalized} {Prisms} and a {New} {Domination} {Invariant}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1165--1178},
     publisher = {mathdoc},
     volume = {41},
     number = {4},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a19/}
}
TY  - JOUR
AU  - Tepeh, Aleksandra
TI  - Total Domination in Generalized Prisms and a New Domination Invariant
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 1165
EP  - 1178
VL  - 41
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a19/
LA  - en
ID  - DMGT_2021_41_4_a19
ER  - 
%0 Journal Article
%A Tepeh, Aleksandra
%T Total Domination in Generalized Prisms and a New Domination Invariant
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 1165-1178
%V 41
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a19/
%G en
%F DMGT_2021_41_4_a19
Tepeh, Aleksandra. Total Domination in Generalized Prisms and a New Domination Invariant. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1165-1178. http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a19/

[1] H.A. Ahangar, J. Amjadi, N. Jafari Rad and V. Samodivkin, Total k-Rainbow domination numbers in graphs, Commun. Comb. Optim. 3 (2018) 37–50. https://doi.org/10.22049/CCO.2018.25719.1021

[2] J. Amjadi, N. Dehgardi, M. Furuya and S.M. Sheikholeslami, A sufficient condition for large rainbow domination number, Int. J. Comput. Math. Comput. Sys. Theory 2 (2017) 53–65. https://doi.org/10.1080/23799927.2017.1330282

[3] J. Azarija, M.A. Henning and S. Klavžar, ( Total ) domination in prisms, Electron. J. Combin. 24 (2017) #P1.19. https://doi.org/10.327236/6288

[4] B. Brešar, T.R. Hartinger, T. Kos and M. Milanič, On total domination in the Cartesian product of graphs, Discuss. Math. Graph Theory 38 (2018) 963–976. https://doi.org/10.7151/dmgt.2039

[5] B. Brešar, Vizing’s conjecture for graphs with domination number 3 —a new proof, Electron. J. Combin. 22 (2015) #P3.38. https://doi.org/10.37236/5182

[6] B. Brešar, Improving the Clark-Suen bound on the domination number of the Cartesian product of graphs, Discrete Math. 340 (2017) 2398–2401. https://doi.org/10.1016/j.disc.2017.05.007

[7] B. Brešar, P. Dorbec, W. Goddard, B.L. Hartnell, M.A. Henning, S. Klavžar and D.F. Rall, Vizing’s conjecture: A survey and recent results, J. Graph Theory 69 (2012) 46–76. https://doi.org/10.1002/jgt.20565

[8] B. Brešar, M.A. Henning and D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008) 213–225. https://doi.org/10.11650/twjm/1500602498

[9] B. Brešar and T.K.Šumenjak, On the 2 -rainbow domination in graphs, Discrete Appl. Math. 155 (2007) 2394–2400. https://doi.org/10.1016/j.dam.2007.07.018

[10] S. Brezovnik and T.K.Šumenjak, Complexity of k-rainbow independent domination and some results on the lexicographic product of graphs, Appl. Math. Comput. 349 (2019) 214–220. https://doi.org/10.1016/j.amc.2018.12.009

[11] K. Choudhary, S. Margulies and I.V. Hicks, A note on total and paired domination of Cartesian product graphs, Electron. J. Combin. 20 (2013) #P25. https://doi.org/10.37236/2535

[12] W. Desormeaux and M.A. Henning, Paired domination in graphs: A survey and recent results, Util. Math. 94 (2014) 101–166.

[13] W. Goddard and M.A. Henning, A note on domination and total domination in prisms, J. Comb. Optim. 35 (2018) 14–20. https://doi.org/10.1007/s10878-017-0150-0

[14] M.A. Henning and D.F. Rall, On the total domination number of Cartesian products of graphs, Graphs Combin. 21 (2005) 63–69. https://doi.org/10.1007/s00373-004-0586-8

[15] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer, New York, 2013). https://doi.org/10.1007/978-1-4614-6525-6

[16] P.T. Ho, A note on the total domination number, Util. Math. 77 (2008) 97–100.

[17] P. Kumbargoudra and J.V. Kureethara, Total k-rainbow domination in graphs, Int. J. Civ. Eng. Technol. 8 (2017) 867–875.

[18] Y. Lu and X. Hou, Total domination in the Cartesian product of a graph and K2 or Cn, Util. Math. 83 (2010) 313–322.

[19] Z. Shao, S.M. Sheikholeslamib, B. Wang, P. Wu and X. Zhang, Trees with equal total domination and 2 -rainbow domination numbers, Filomat 32 (2018) 599–607. https://doi.org/10.2298/FIL1802599S

[20] T.K. Šumenjak, D.F. Rall and A. Tepeh, On k-rainbow independent domination in graphs, Appl. Math. Comput. 333 (2018) 353–361. https://doi.org/10.1016/j.amc.2018.03.113