## Regular subgraphs of hypercubes.(English)Zbl 0977.05035

From the author’s abstract: 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 bipartion $$(X,Y)$$ is given by $$X=$$ even vertices and $$Y=$$ odd vertices.) Thus we consider the cases $$r=3,5$$, and 7. We find that $$H_{k,3}$$ is a subgraph of a hypercube precisely when $$k\equiv 0$$ (mod 4). $$H_{k,5}$$ can be embedded in a hypercube precisely when $$k\equiv 0$$ (mod 16). For $$r=7$$ we show that $$H_{k,7}$$ is embeddable in a hypercube whenever $$k\equiv 0$$ (mod 16).