In 1979 Tarsi showed that an edge decomposition of a complete multigraph into stars of size m exists whenever some obvious necessary conditions hold. In 1992 Lonc gave necessary and sufficient conditions for the existence of an edge decomposition of a (simple) complete graph into stars of sizes m1,…,mt. We show that the general problem of when a complete multigraph admits a decomposition into stars of sizes m1,…,mt is NP-complete, but that it becomes tractable if we place a strong enough upper bound on max(m1,…,mt). We determine the upper bound at which this transition occurs. Along the way we also give a characterisation of when an arbitrary multigraph can be decomposed into stars of sizes m1,…,mt with specified centres, and a generalisation of Landau's theorem on tournaments.
- Complete multigraph
- Edge decomposition