Decompositions of complete multigraphs into stars of varying sizes (Q2200917)

An \(m\)-star is a complete bipartite graph \(K_{1,m}\); for an integer \(\lambda\ge1\), \(\lambda K_n\) denotes the multigraph obtained from the underlying graph \(K_n\) by assigning to each of its edges the multiplicity \(\lambda\). This paper generalizes to multigraphs a numerical characterization [\textit{Z. Lonc}, J. Comb. Theory, Ser. A 61, No. 2, 263--278 (1992; Zbl 0763.04004); \textit{C. Lin} and \textit{T.-W. Shyu}, J. Graph Theory 23, No. 4, 361--364 (1996; Zbl 0880.05069)] for the existence of a decomposition of \(K_n\) into stars of specified sizes. The authors formulate a primary question, \((\lambda,\alpha)\)-STAR DECOMP, as a family of decision problems, one for each integer \(\lambda\ge1\) and real \(\alpha\in{\mathbb R}\) such that \(0\le\alpha\le1\): if \(n\) and \(m_1,\dots,m_t\) are positive integers such that \(\max\left\{m_1,\dots,m_t\right\}\le\alpha(n-1)\) and \(m_1+\dots+m_t=\lambda\cdot {\binom n 2}\), does the multigraph \(\lambda K_n\) admit a decomposition into disjoint stars of sizes \(m_1,\dots,m_t\)? The main theorem is: Theorem 1: Let \(\lambda\ge2\). Then \((\lambda,\alpha)\)-STAR DECOMP is NP-complete if \(\alpha>\alpha^\prime\), where \(\alpha^\prime=\frac\lambda{\lambda+1}\) if \(\lambda\) is odd, and \(\alpha^\prime=1-\frac2\lambda\cdot\left(3-2\sqrt{2}\right)\) if \(\lambda\) is even. Furthermore, if \(\alpha\le\alpha^\prime\), then every instance of \((\lambda,\alpha)\)-STAR DECOMP is feasible and the required decompositions can be constructed in polynomial time. This theorem is proved as a consequence of a second theorem, as another application of which the authors are able to generalize to orientations of a multigraph a theorem of Landau which characterises when there exists a 1-fold tournament with specified degrees [\textit{H. G. Landau}, ``On dominance relations and the structure of animal societies. III: The condition for a score structure'', Bull. Math. Biophys. 15, 143--148 (1953; \url{doi:10.1007/BF02476378})].