betaFeedback

WorksMathematics

Star decomposition of complete multipartite graphs

Abstract

We study minimum degree-sum conditions for decompositions into stars of sizes kk and k+1k+1, where k≥3k\ge3. Write σ(G)=min⁡uv∈E(G)(d(u)+d(v))σ(G)=\min_{uv\in E(G)}(d(u)+d(v)), and let ckc_k be the least integer threshold guaranteeing a {K1,k,K1,k+1}\{K_{1,k},K_{1,k+1}\}-decomposition for every finite simple graph. Using Tarsi's sufficient condition, we prove that KnK_n admits such a decomposition whenever n≥2kn\ge2k. Together with the obstruction K2k−1K_{2k-1} of Zhao and Wu, this gives the optimal integer threshold 4k−34k-3 for complete graphs. For complete multipartite graphs, we establish the sufficiency of σ(G)≥9σ(G)\ge9 when k=3k=3 by a finite computational verification and an extension argument. For every k≥3k\ge3, the complete tripartite graph Gk=Kk2−k−1,k−2,1G_k=K_{k^2-k-1,k-2,1} satisfies σ(Gk)=k2−1σ(G_k)=k^2-1 and has no such decomposition. Consequently, ck≥k2c_k\ge k^2, even when the class is restricted to complete multipartite graphs. The optimal integer threshold in this class is therefore 99 for k=3k=3. Sufficiency of σ(G)≥k2σ(G)\ge k^2 for complete multipartite graphs with k≥4k\ge4, and the exact values of ckc_k for general graphs, remain open in this study.

Paper details

vlnc:W_6q5z63cr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…