Geodesic
On Total Domination in the Cartesian Product of Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 963-976.

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

Ho proved in [A note on the total domination number, Util. Math. 77 (2008) 97–100] that the total domination number of the Cartesian product of any two graphs without isolated vertices is at least one half of the product of their total domination numbers. We extend a result of Lu and Hou from [Total domination in the Cartesian product of a graph and K_2 or C_n, Util. Math. 83 (2010) 313–322] by characterizing the pairs of graphs G and H for which γ_t (G □ H)=1/2 γ_t (G) γ_t (H), whenever γ_t (H) = 2. In addition, we present an infinite family of graphs G_n with γ_t (G_n) = 2n, which asymptotically approximate equality in γ_t (G_n □ H_n ) ≥ 1/2 γ_t (G_n)^2.
Keywords: total domination, Cartesian product, total domination quotient 
@article{DMGT_2018_38_4_a6,
     author = {Bre\v{s}ar, Bo\v{s}tjan and Hartinger, Tatiana Romina and Kos, Tim and Milani\v{c}, Martin},
     title = {On {Total} {Domination} in the {Cartesian} {Product} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {963--976},
     publisher = {mathdoc},
     volume = {38},
     number = {4},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a6/}
}
TY  - JOUR
AU  - Brešar, Boštjan
AU  - Hartinger, Tatiana Romina
AU  - Kos, Tim
AU  - Milanič, Martin
TI  - On Total Domination in the Cartesian Product of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 963
EP  - 976
VL  - 38
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a6/
LA  - en
ID  - DMGT_2018_38_4_a6
ER  - 
%0 Journal Article
%A Brešar, Boštjan
%A Hartinger, Tatiana Romina
%A Kos, Tim
%A Milanič, Martin
%T On Total Domination in the Cartesian Product of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 963-976
%V 38
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a6/
%G en
%F DMGT_2018_38_4_a6
Brešar, Boštjan; Hartinger, Tatiana Romina; Kos, Tim; Milanič, Martin. On Total Domination in the Cartesian Product of Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 963-976. http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a6/

[1] 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. doi:10.1002/jgt.20565

[2] B. Brešar, M.A. Henning and D.F. Rall, Paired-domination of Cartesian products of graphs and rainbow domination, Electron. Notes Discrete Math. 22 (2005) 233–237. doi:10.1016/j.endm.2005.06.059

[3] R.C. Brigham, J.R. Carrington and R.P. Vitray, Connected graphs with maximum total domination number, J. Combin. Math. Combin. Comput. 34 (2000) 81–96.

[4] M. Dorfling, W. Goddard, M.A. Henning and C.M. Mynhardt, Construction of trees and graphs with equal domination parameters, Discrete Math. 306 (2006) 2647–2654. doi:10.1016/j.disc.2006.04.031

[5] W. Goddard, Automated bounds on recursive structures, Util. Math. 75 (2008) 193–210.

[6] M.A. Henning, Trees with large total domination number, Util. Math. 60 (2001) 99–106.

[7] M.A. Henning, A survey of selected recent results on total domination in graphs, Discrete Math. 309 (2009) 32–63. doi:10.1016/j.disc.2007.12.044

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

[9] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, 2013). doi:10.1007/978-1-4614-6525-6

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

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