k-star Decompositions of Lambda-Fold Complete Multipartite Graphs

Abstract

We examine the problem of k-star decompositions on lambda-fold complete multipartite graphs. After a brief examination of the computational complexity issues involved, we present complete proofs for necessary and sufficient conditions in the case where k = 2 and the case where lambda = 2 and k = 3. We then show some partial results for k = 3 and higher values of lambda along with some helpful tools, including some necessary conditions, which may help in solving further cases.