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)\le 2k{\gamma }_{\times k,t}(G\square H)$ provided ${\gamma }_{\times k,t}(G)\le 2k\rho (G)$, where $\rho$ is the packing number. We also give bounds on ${\gamma }_{\times k,t}(G\square H)$ in terms of (open) packing numbers, and consider the extremal case of ${\gamma }_{\times k,t}(K_n\square K_m)$, i.e., the rook's graph, giving a constructive proof of a general formula for ${\gamma }_{\times 2,t}(K_n\square K_m)$.

18 pages