zbMATH — the first resource for mathematics

On total domination in the Cartesian product of graphs. (English) Zbl 1392.05086
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.)
Full Text:
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
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.