Star decomposition of complete multipartite graphs
Source: arxiv.org/abs/2611.24973
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$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.24973
curl -X POST /api/v1/records/arxiv/2611.24973/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.24973/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'