Cartesian product graphs and k-tuple total domination

Abstract

‎A $k$-tuple total dominating set ($k$TDS) of a graph $G$ is a set $S$ of vertices in which every vertex in $G$ is adjacent to at least $k$ vertices in $S$; the minimum size of a $k$TDS is denoted $\gamma_{\times k,t}(G)$‎. ‎We give a Vizing-like inequality for Cartesian product graphs‎, ‎namely $\gamma_{\times k,t}(G) \gamma_{\times k,t}(H) \leq 2k \gamma_{\times k,t}(G \Box H)$ provided $\gamma_{\times k,t}(G) \leq 2k\rho(G)$‎, ‎where $\rho$ is the packing number‎. ‎We also give bounds on $\gamma_{\times k,t}(G \Box H)$ in terms of (open) packing numbers‎, ‎and consider the extremal case of $\gamma_{\times k,t}(K_n \Box K_m)$‎, ‎i.e.‎, ‎the rook's graph‎, ‎giving a constructive proof of a general formula for $\gamma_{\times 2‎, ‎t}(K_n \Box K_m)$‎.