Regular subgraphs of hypercubes. (English) Zbl 0977.05035

Ramras, Mark

Ars Comb. 52, 21-32 (1999).

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).

Reviewer: Ladislav Nebeský

MSC:

05C10

Planar graphs; geometric and topological aspects of graph theory

Keywords:

regular graph; embedding; hypercube