Regular Subgraphs of Hypercubes

Abstract

We consider several families of regular bipartite graphs, most of which are vertex-transitive, and investigate the problem of determining which ones are subgraphs of hypercubes. We define $H_{k,r}$ as the graph on $k$ vertices $0,1,2,\dots ,k-1$ which form a $k$-cycle (when traversed in that order), with the additional edges $(i,i+r)$ for $i$ even, where $i+r$ is computed modulo $k$. Since this graph contains both a $k$-cycle and an $(r+1)$-cycle, it is bipartite (if and only if) $k$ is even and $r$ is odd. (For the “if” part, the bipartition $(X,Y)$ is given by $X=$ even vertices and $Y=$ odd vertices.) Thus we consider only the cases $r=3,5,7$. We find that $H_{k,3}$ is a subgraph of a hypercube precisely when $k\equiv 0(\mathrm{mod}4)$. $H_{k,5}$ can be embedded in a hypercube precisely when $k\equiv 0(\mathrm{mod}16)$. For $r=7$ we show that $H_{k,7}$ is embeddable in a hypercube whenever $k\equiv 0(\mathrm{mod}16)$.