Advanced Search

Let $G$ be a multigraph. The star number $\mathrm{s}\left(G\right)$ of $G$ is the minimum number of stars needed to decompose the edges of $G$. The star arboricity $\mathrm{s}a\left(G\right)$ of $G$ is the minimum number of star forests needed to decompose the edges of $G$. As usual $\lambda K_n$ denote the $\lambda$-fold complete graph on $n$ vertices (i.e., the multigraph on $n$ vertices such that there are $\lambda$ edges between every pair of vertices). In this paper, we prove that for $n\ge 2$ $$\begin{array}{ccc}\hfill \mathrm{s}\left(\lambda K_n\right)& =\left\}\begin{array}{ccc}\frac{1}{2}\lambda n\hfill & \text{if}\lambda \text{is}\text{even},\frac{1}{2}(\lambda +1)n-1\hfill & \text{if}\lambda \text{is}\text{odd,}\end{array}\right.\mathrm{s}a\left(\lambda K_n\right)\hfill & \hfill =\left\}\begin{array}{ccc}\lceil \frac{1}{2}\lambda n\rceil \hfill & \text{if}\lambda \text{is}\text{odd},n=2,3\text{or}\lambda \text{is}\text{even},\lceil \frac{1}{2}\lambda n\rceil +1\hfill & \text{if}\lambda \text{is}\text{odd},n\ge 4.\end{array}\right.\end{array}(1,2)$$