Star decomposition of complete multipartite graphs
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.