Home > Timetable > Contribution details


Decomposing complete multigraphs into stars of varying sizes


  • Dr. Daniel HORSLEY

Primary authors


In 1979 Tarsi showed that an edge decomposition of a complete multigraph into stars of size $k$ exists whenever the obvious necessary conditions hold. In 1996 Lin and Shyu gave necessary and sufficient conditions for the existence of an edge decomposition of a (simple) complete graph into stars of sizes $m_1,\ldots,m_t$.

I will discuss the common generalisation of these problems: when does a complete multigraph admit an edge decomposition into stars of sizes $m_1,\ldots,m_t$? This problem exhibits more complicated and interesting behaviour than either of its specialisations.