Regular Subgraphs of Hypercubes

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,\ldots,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 \pmod{4}\). \(H_{k,5}\) can be embedded in a hypercube precisely when \(k \equiv 0 \pmod{16}\). For \(r = 7\) we show that \(H_{k,7}\) is embeddable in a hypercube whenever \(k \equiv 0 \pmod{16}\).