Star number and star arboricity of a complete multigraph

Lin, Chiang ; Shyu, Tay-Woei

Czechoslovak Mathematical Journal, Tome 56 (2006) no. 3, pp. 961-967

Résumé

Let $G$ be a multigraph. The star number ${\mathrm s}(G)$ of $G$ is the minimum number of stars needed to decompose the edges of $G$. The star arboricity ${\mathrm sa}(G)$ 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{aligned} {\mathrm s}(\lambda K_n)= \left\rbrace \begin{array}{ll}\frac{1}{2}\lambda n\text{if}\ \lambda \ \text{is even}, \frac{1}{2}(\lambda +1)n-1\text{if}\ \lambda \ \text{is odd,} \end{array}\right. {\vspace{2.0pt}} {\mathrm sa}(\lambda K_n)= \left\rbrace \begin{array}{ll}\lceil \frac{1}{2}\lambda n \rceil \text{if}\ \lambda \ \text{is odd},\ n = 2, 3 \ \text{or}\ \lambda \ \text{is even}, \lceil \frac{1}{2}\lambda n \rceil +1 \text{if}\ \lambda \ \text{is odd},\ n\ge 4. \end{array}\right. \end{aligned} \qquad \mathrm{(1,2)}\]

Détail

Classification : 05C70
Keywords: decomposition; star arboricity; star forest; complete multigraph