A Note on Integer Domination of Cartesian Product Graphs

Abstract

Given a graph $G$, a dominating set $D$ is a set of vertices such that any vertex in $G$ has at least one neighbor (or possibly itself) in $D$. A $k$-dominating multiset $D_k$ is a multiset of vertices such that any vertex in $G$ has at least $k$ vertices from its closed neighborhood in $D_k$ when counted with multiplicity. In this paper, we utilize the approach developed by Clark and Suen (2000) and properties of binary matrices to prove a "Vizing-like" inequality on minimum $k$-dominating multisets of graphs $G,H$ and the Cartesian product graph $G\square H$. Specifically, denoting the size of a minimum $k$-dominating multiset as ${\gamma }_k(G)$, we demonstrate that ${\gamma }_k(G){\gamma }_k(H)\le 2k{\gamma }_k(G\square H)$.