Star decompositions of cubes (Q5936091)

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