← ALB News · curated headline

Star decomposition of complete multipartite graphs

arXiv Mathematics · WORLD · Mathematics · 11/20/2026, 12:00:00 AM

arXiv:2611.24973v1 Announce Type: new Abstract: We study minimum degree-sum conditions for decompositions into stars of sizes $k$ and $k+1$, where $k\ge3$. Write $\sigma(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 $\sigma(G)\ge9$ when $k=3$ by a finite computational verification and an extension argument. For every $k\ge3$, the complete tripartite graph $G_k=K_{k^2-k-1,k-2,1}$ satisfies $\sigma(G_k)=k^2-1$ and has no such decomposition. Consequently, $c_k\ge k^2$, even when the class is restricted to complete multipartite graphs. The optimal integer threshold in this class is therefore $9$ for $k=3$. Sufficiency of $\sigma(G)\ge k^2$ for complete multipartite graphs with $k\ge4$, and the exact values of $c_k$ for general graphs, remain open in this study.

Continue to arXiv Mathematics →

You are being forwarded in 6s — stay on this page