Hypercubes As Direct Products

Abstract

Let G be a connected bipartite graph. An involution $\alpha$ of G that preserves the bipartition of G is called bipartite. Let $G^\alpha$ be the graph obtained from G by adding to G the natural perfect matching induced by $\alpha$. We show that the k-cube Qk is isomorphic to the direct product $G \times H$ if and only if G is isomorphic to $Q_{k-1}^\alpha$ for some bipartite involution $alpha$ of $Q_{k-1}$ and H=K2 .