Authors: B. Bre¹ar, T.R. Hartinger, T. Kos, M. Milanič Title: On total domination in the Cartesian product of graphs Source: Discussiones Mathematicae Graph Theory Received 03.08.2016, Revised 28.12.2016, Accepted 25.03.2017, doi: 10.7151/dmgt.2039 | |
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 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}GH=\frac{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 \hbox{γ_{t}(G_{n}\Box G_{n})≥ \frac{1}{2}γ_{t}(G_{n})^{2}}. | |
Keywords: total domination, Cartesian product, total domination quotient | |
Links: |