Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
decomposition; star arboricity; star forest; complete multigraph
decomposition; star arboricity; star forest; complete multigraph
Summary:
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)}\]
References:
[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 0778395
[2] I. Algor, N. Alon: The star arboricity of graphs. Discrete Math. 75 (1989), 11–22. DOI 10.1016/0012-365X(89)90073-3 | MR 1001381
[3] Y. Aoki: The star-arboricity of the complete regular multipartite graphs. Discrete Math. 81 (1990), 115–122. DOI 10.1016/0012-365X(90)90142-5 | MR 1054968 | Zbl 0737.05038
[4] B. Bollobás: Extremal Graph Theory. Academic Press, New York, 1978. MR 0506522
[5] J. A. Bondy, U. S. R. Murty: Graph Theory with Applications. North Holland, New York, 1976. MR 0411988
[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 10.1016/0012-365X(86)90190-1 | MR 0820842
[7] H. Enomoto, Y. Usami: The star arboricity of complete bipartite graphs. Graph Theory, Combinatorics and Applications 1 (1988), 389–396. MR 1170792
[8] J. Hagauer, S. Klavžar: On independence numbers of the Cartesian product of graphs. ARS Combin. 43 (1996), 149–157. MR 1415983
[9] S. L. Hakimi, J. Mitchem, E. Schmeichel: Star arboricity of graphs. Discrete Math. 149 (1996), 93–98. DOI 10.1016/0012-365X(94)00313-8 | MR 1375101
[10] P. K. Jha, S. Klavžar: Independence in direct-product graphs. ARS Combin. 50 (1998), 53–63. MR 1670588
[11] C. Lin, J.-J. Lin, and H.-C. Lee: Some decomposition invariants of crowns. ARS Combin. 66 (2003), 33–48. MR 1961473
[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 1724509
[13] K.-W. Lih, D.-F. Liu, and X. Zhu: Star extremal circulant graphs. SIAM J. Discrete Math. 12 (1999), 491–499. DOI 10.1137/S0895480198342838 | MR 1720404
[14] C. St. J. A. Nash-Williams: Decomposition of finite graphs into forests. J. London Math. Soc. 39 (1964), 12. MR 0161333 | Zbl 0119.38805
[15] M. Truszczynski: Decomposing graphs into forests of stars. Congr. Numer. 54 (1986), 73–86. MR 0885263 | Zbl 0646.05022
Search
Partner of
