Geodesic
Star number and star arboricity of a complete multigraph
Czechoslovak Mathematical Journal, Tome 56 (2006) no. 3, pp. 961-967
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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)}\]
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)}\]
Classification : 05C70
Keywords: decomposition; star arboricity; star forest; complete multigraph 
@article{CMJ_2006_56_3_a14,
     author = {Lin, Chiang and Shyu, Tay-Woei},
     title = {Star number and star arboricity of a complete multigraph},
     journal = {Czechoslovak Mathematical Journal},
     pages = {961--967},
     year = {2006},
     volume = {56},
     number = {3},
     mrnumber = {2261668},
     zbl = {1164.05433},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2006_56_3_a14/}
}
TY  - JOUR
AU  - Lin, Chiang
AU  - Shyu, Tay-Woei
TI  - Star number and star arboricity of a complete multigraph
JO  - Czechoslovak Mathematical Journal
PY  - 2006
SP  - 961
EP  - 967
VL  - 56
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/CMJ_2006_56_3_a14/
LA  - en
ID  - CMJ_2006_56_3_a14
ER  - 
%0 Journal Article
%A Lin, Chiang
%A Shyu, Tay-Woei
%T Star number and star arboricity of a complete multigraph
%J Czechoslovak Mathematical Journal
%D 2006
%P 961-967
%V 56
%N 3
%U http://geodesic.mathdoc.fr/item/CMJ_2006_56_3_a14/
%G en
%F CMJ_2006_56_3_a14
Lin, Chiang; Shyu, Tay-Woei. Star number and star arboricity of a complete multigraph. Czechoslovak Mathematical Journal, Tome 56 (2006) no. 3, pp. 961-967. http://geodesic.mathdoc.fr/item/CMJ_2006_56_3_a14/

[1] J. Akiyama, M.  Kano: Path factors of a graph. In: Graphs and Applications. Proceedings of the first Cororado Symposium on Graph Theory, F. Harary, J.  Maybee (eds.), , , 1982, pp. 1–21. | MR

[2] I. Algor, N.  Alon: The star arboricity of graphs. Discrete Math. 75 (1989), 11–22. | DOI | MR

[3] Y. Aoki: The star-arboricity of the complete regular multipartite graphs. Discrete Math. 81 (1990), 115–122. | DOI | MR | Zbl

[4] B.  Bollobás: Extremal Graph Theory. Academic Press, New York, 1978. | MR

[5] J. A. Bondy, U. S. R.  Murty: Graph Theory with Applications. North Holland, New York, 1976. | MR

[6] Y.  Egawa, T.  Fukuda, S.  Nagoya, M.  Urabe: A decomposition of complete bipartite graphs into edge-disjoint subgraphs with star components. Discrete Math. 58 (1986), 93–95. | DOI | MR

[7] H. Enomoto, Y.  Usami: The star arboricity of complete bipartite graphs. Graph Theory, Combinatorics and Applications 1 (1988), 389–396. | MR

[8] J. Hagauer, S.  Klavžar: On independence numbers of the Cartesian product of graphs. ARS Combin. 43 (1996), 149–157. | MR

[9] S. L. Hakimi, J.  Mitchem, E.  Schmeichel: Star arboricity of graphs. Discrete Math. 149 (1996), 93–98. | DOI | MR

[10] P. K. Jha, S.  Klavžar: Independence in direct-product graphs. ARS Combin. 50 (1998), 53–63. | MR

[11] C. Lin, J.-J.  Lin, and H.-C.  Lee: Some decomposition invariants of crowns. ARS Combin. 66 (2003), 33–48. | MR

[12] C.  Lin, J.-J. Lin, T.-W. Shyu: Isomorphic star decomposition of multicrowns and the power of cycles. ARS Combin. 53 (1999), 249–256. | MR

[13] K.-W. Lih, D.-F.  Liu, and X.  Zhu: Star extremal circulant graphs. SIAM J.  Discrete Math. 12 (1999), 491–499. | DOI | MR

[14] C. St. J. A. Nash-Williams: Decomposition of finite graphs into forests. J. London Math. Soc. 39 (1964), 12. | MR | Zbl

[15] M.  Truszczynski: Decomposing graphs into forests of stars. Congr. Numer. 54 (1986), 73–86. | MR | Zbl