Decompositions of complete multigraphs into stars of varying sizes

Rosalind A. Cameron, Daniel Horsley

Research output: Contribution to journalArticleResearchpeer-review

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

Original languageEnglish
Pages (from-to)32-64
Number of pages33
JournalJournal of Combinatorial Theory, Series B
Volume145
DOIs
Publication statusPublished - Nov 2020

Keywords

  • Complete multigraph
  • Edge decomposition
  • NP-completeness
  • Star
  • Tournament

Cite this