×

zbMATH — the first resource for mathematics

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.)
Keywords:
decomposition
PDF BibTeX XML Cite
Full Text: DOI