(Total) domination in prisms (Q510330)

Summary: Using 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 bipartiteness condition is essential by constructing, for any \(k \geq 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.