Delphi.science

Star decomposition of complete multipartite graphs

Source: arxiv.org/abs/2611.24973

Juho Lee

arXivarxiv/2611.24973Nov 17, 2026math.COscore 0

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$…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'