## Star decompositions of cubes.(English)Zbl 0984.05069

A decomposition of a graph $$G$$ is a sequence $$G_1,G_2,\dots, G_t$$ of subgraphs of $$G$$ whose edge sets partition the edge set of $$G$$. Let $$S_k$$ denote the star with $$k$$ edges, and let $$Q_n$$ denote the $$n$$-cube. The authors prove that the obvious necessary conditions for the existence of an $$S_k$$ decomposition of $$Q_n$$ are sufficient. In particular, they show that if $$k$$ and $$n$$ are positive integers then there is an $$S_k$$ decomposition of $$Q_n$$ if and only if $$k\leq n$$ and $$k$$ divides the number of edges of $$Q_n$$.

### MSC:

 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

decomposition
Full Text: