(Total) Domination in Prisms

Abstract

With the aid of hypergraph transversals it is proved that ${\gamma }_t(Q_{n+1})=2\gamma (Q_n)$, where ${\gamma }_t(G)$ and $\gamma (G)$ denote the total domination number and the domination number of $G$, respectively, and $Q_n$ is the $n$-dimensional hypercube. More generally, it is shown that if $G$ is a bipartite graph, then ${\gamma }_t(G\square K_2)=2\gamma (G)$. Further, we show that the bipartite condition is essential by constructing, for any $k\ge 1$, a (non-bipartite) graph $G$ such that ${\gamma }_t(G\square K_2)=2\gamma (G)-k$. Along the way several domination-type identities for hypercubes are also obtained.