On total domination in the Cartesian product of graphs. (English) Zbl 1392.05086

Brešar, Boštjan; Hartinger, Tatiana Romina; Kos, Tim; Milanič, Martin

Discuss. Math., Graph Theory 38, No. 4, 963-976 (2018).

Summary: Ho proved in [P. T. Ho, Util. Math. 77, 97–100 (2008; Zbl 1161.05056)] 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 Y. Lu and X. Hou [ibid. 83, 313–322 (2010; Zbl 1242.05208)] by characterizing the pairs of graphs \(G\) and \(H\) for which \(\gamma _t \left( G\square H \right) = {1 \over 2}\gamma _t \left( G \right)\gamma _t \left( H \right)\), whenever \(\gamma_t(H) = 2\). In addition, we present an infinite family of graphs \(G_n\) with \(\gamma_t(G_n) = 2n\), which asymptotically approximate equality in \(\gamma _t \left( {G_n \square H_n } \right) \geq {1 \over 2}\gamma _t \left( {G_n } \right)^2 \).

MSC:

05C69	Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C76	Graph operations (line graphs, products, etc.)

Keywords:

total domination; Cartesian product; total domination quotient

References:

[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 · Zbl 1234.05173
[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 · Zbl 1200.05154
[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. · Zbl 0958.05100
[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 · Zbl 1104.05053
[5]	W. Goddard, Automated bounds on recursive structures, Util. Math. 75 (2008) 193-210. · Zbl 1152.90640
[6]	M.A. Henning, Trees with large total domination number, Util. Math. 60 (2001) 99-106. · Zbl 1011.05045
[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 · Zbl 1219.05121
[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 · Zbl 1408.05002
[10]	P.T. Ho, A note on the total domination number, Util. Math. 77 (2008) 97-100. · Zbl 1161.05056
[11]	Y. Lu and X. Hou, Total domination in the Cartesian product of a graph and K_2or C_n, Util. Math. 83 (2010) 313-322. · Zbl 1242.05208