Cartesian product graphs and k-tuple total domination


Adel P Kazemi, Behnaz Pahlavsay, Rebecca J Stones




A k-tuple total dominating set (kTDS) 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 kTDS is denoted γ ×k,t (G). We give a Vizing-like inequality for Cartesian product graphs, namely γ ×k,t (G)γ ×k,t (H) ≤ 2kγ ×k,t (GH) provided γ ×k,t (G) ≤ 2kρ(G) holds, where ρ denotes the packing number. We also give bounds on γ ×k,t (GH) in terms of (open) packing numbers, and consider the extremal case of γ ×k,t (K n K m), i.e., the rook's graph, giving a constructive proof of a general formula for γ ×2,t (K n K m).