Multistar Decomposition of Complete Multigraphs

Abstract

In this paper, we consider the problem of decomposing complete multigraphs into multistars (a multistar is a star with multiple edges allowed). We obtain a criterion for the decomposition of the complete multigraph \(\lambda K_n\), into multistars with prescribed number of edges, but the multistars in the decomposition with the same number of edges are not necessarily isomorphic. We also consider the problem of decomposing \(\lambda K_n\) into isomorphic multistars and propose a conjecture about the decomposition of \(2K_n\) into isomorphic multistars.