학술

Star decomposition of complete multipartite graphs

arXiv Math
CC BY
이 매체는 공공·자유 라이선스로 본문을 직접 표시합니다.

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.

관련 뉴스