Edge Decompositions of Hypercubes by Paths

Abstract

Many authors have investigated edge decompositions of graphs by the edge sets of isomorphic copies of special subgraphs. For $q$- dimensional hypercubes $Q_q$ various researchers have done this for cer- tain trees, paths, and cycles. In this paper we shall say that "$H$ divides $G$" if $E(G)$ is the disjoint union of $\{fE(H_i)|H_i\simeq H\}$. Our main result is that for $q$ odd and $q<2^{32}$, the path of length $m$, $P_m$, divides $Q_q$ if and only if $m\le q$ and $m|(q\times 2^{q-1})$.

Cited by in corpus (2)

• Decomposing the vertex set of a hypercube into isomorphic subgraphs
• Decomposing the cube into paths