Edge Decompositions of Hypercubes by Paths and by Cycles

Original · EN

If H is (or is isomorphic to) a subgraph of G, H is said to divide G if there is an edge-decomposition of G by copies of E(H), the edge set of H. A more restrictive version of this is when there is a subgroup H of Aut (G), the automorphism group of G, such that the copies of E(H) are the translates of E(H) by the elements of H. In a paper by the second author, this situation was described by saying that H, or more precisely E(H), is a fundamental set for G. Many authors have studied the notion of divisibility for various graphs, and in particular for various subgraphs of hypercubes, such as paths, trees, and cycles. We continue such a study in this paper; both for divisibilty, and, when possible, for fundamental sets. The final section of the paper lists our main results.