Decomposing complete multigraphs into stars of varying sizes

Not scheduled
UP FHS (Koper)



Titov trg 5,Koper


Dr Daniel Horsley (Monash University)


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.

Primary authors

Dr Daniel Horsley (Monash University) Dr Rosalind Cameron (Memorial University)

Presentation Materials

There are no materials yet.