On total domination in the Cartesian product of graphs

2016/07/07 by Brešar, Boštjan, Hartinger, Tatiana Romina, Kos, Tim +1
#05C69 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1607.01909

Abstract

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 with no 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₂ or C_n, Util. Math. 83 (2010) 313--322] by characterizing the pairs of graphs G and H for which γ_t(G\Box 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 the equality in γ_t(G_n\Box G_n)≥ (1)/(2)γ_t(G_n)².

Related

• A Note on Total and Paired Domination of Cartesian Product Graphs
• Total k-domination in Cartesian product of complete graphs
• An Improved Bound for Upper Domination of Cartesian Products of Graphs
• On the domination number of the cartesian product of the path graph and any pair of graphs
• Graphs which satisfy a Vizing-like bound for power domination of Cartesian products