Decompositions of complete multigraphs into stars of varying sizes

Abstract

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 $m_1,\dots ,m_t$. We show that the general problem of when a complete multigraph admits a decomposition into stars of sizes $m_1,\dots ,m_t$ is $\mathsf{NP}$-complete, but that it becomes tractable if we place a strong enough upper bound on $\max (m_1,\dots ,m_t)$. 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 $m_1,\dots ,m_t$ with specified centres, and a generalisation of Landau's theorem on tournaments.

30 pages, 0 figures