Multigraph decomposition into stars and into multistars

AbstractWe study the decomposition of multigraphs with a constant edge multiplicity into copies of a fixed star H=K1,t: We present necessary and sufficient conditions for such a decomposition to exist where t=2 and prove NP-completeness of the corresponding decision problem for any t⩾3. We also prove NP-completeness when the edge multiplicity function is not restricted either on the input G or on the fixed multistar H