WorksMathematics
Star decomposition of complete multipartite graphs
Abstract
We study minimum degree-sum conditions for decompositions into stars of sizes and , where . Write , and let be the least integer threshold guaranteeing a -decomposition for every finite simple graph. Using Tarsi's sufficient condition, we prove that admits such a decomposition whenever . Together with the obstruction of Zhao and Wu, this gives the optimal integer threshold for complete graphs. For complete multipartite graphs, we establish the sufficiency of when by a finite computational verification and an extension argument. For every , the complete tripartite graph satisfies and has no such decomposition. Consequently, , even when the class is restricted to complete multipartite graphs. The optimal integer threshold in this class is therefore for . Sufficiency of for complete multipartite graphs with , and the exact values of for general graphs, remain open in this study.