On decomposition of multistars into multistars

Abstract

The multistar $ S^{w_1,...,w_n}$ is the multigraph whose underlying graph is an $n$-star and the multiplicities of its $n$ edges are $ w_1,..., w_n$. Let $G$ and $H$ be two multigraphs. An $H$-decomposition of $G$ is a set $D$ of $H$-subgraphs of $G$, such that the sum of $\omega(e)$ over all graphs in $D$ which include an edge $e$, equals the multiplicity of $e$ in $G$, for all edges $e$ in $G$. In this paper, we fully characterize $S^{1,2,3}, K_{1,m}$ and $S^{m^{l}}$ decomposable multistars, where $m^l$ is $m$ repeated $l$ times.

Keywords

• decomposition
• multigraph
• multistar