A Note on Total and Paired Domination of Cartesian Product Graphs

Abstract

A dominating set $D$ for a graph $G$ is a subset of $V(G)$ such that any vertex not in $D$ has at least one neighbor in $D$. The domination number $\gamma (G)$ is the size of a minimum dominating set in $G$. Vizing's conjecture from 1968 states that for the Cartesian product of graphs $G$ and $H$, $\gamma (G)\gamma (H)\le \gamma (G\square H)$, and Clark and Suen (2000) proved that $\gamma (G)\gamma (H)\le 2\gamma (G\square H)$. In this paper, we modify the approach of Clark and Suen to prove a variety of similar bounds related to total and paired domination, and also extend these bounds to the $n$-Cartesian product of graphs $A^1$ through $A^n$.