{"id":"arxiv/2611.24973","url":"https://arxiv.org/abs/2611.24973","tags":["math.CO"],"score":0,"title":"Star decomposition of complete multipartite graphs","domain":"math.CO","source":"arxiv","authors":["Juho Lee"],"reviews":0,"subject":"math.CO","summary":"We study minimum degree-sum conditions for decompositions into stars of sizes $k$ and $k+1$, where $k\\ge3$. Write $σ(G)=\\min_{uv\\in E(G)}(d(u)+d(v))$, and let $c_k$ be the least integer threshold guaranteeing a $\\{K_{1,k},K_{1,k+1}\\}$-decomposition for every finite simple graph. Using Tarsi's sufficient condition, we prove that $K_n$ admits such a decomposition whenever $n\\ge2k$. Together with the obstruction $K_{2k-1}$ of Zhao and Wu, this gives the optimal integer threshold $4k-3$ for complete graphs. For complete multipartite graphs, we establish the sufficiency of $σ(G)\\ge9$ when $k=3$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-17","reactions":{}}