| Title:
|
Star number and star arboricity of a complete multigraph (English) |
| Author:
|
Lin, Chiang |
| Author:
|
Shyu, Tay-Woei |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
56 |
| Issue:
|
3 |
| Year:
|
2006 |
| Pages:
|
961-967 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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)}\] (English) |
| Keyword:
|
decomposition |
| Keyword:
|
star arboricity |
| Keyword:
|
star forest |
| Keyword:
|
complete multigraph |
| MSC:
|
05C70 |
| idZBL:
|
Zbl 1164.05433 |
| idMR:
|
MR2261668 |
| . |
| Date available:
|
2009-09-24T11:40:12Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/128121 |
| . |
| Reference:
|
[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 |
| Reference:
|
[2] I. Algor, N. Alon: The star arboricity of graphs.Discrete Math. 75 (1989), 11–22. MR 1001381, 10.1016/0012-365X(89)90073-3 |
| Reference:
|
[3] Y. Aoki: The star-arboricity of the complete regular multipartite graphs.Discrete Math. 81 (1990), 115–122. Zbl 0737.05038, MR 1054968, 10.1016/0012-365X(90)90142-5 |
| Reference:
|
[4] B. Bollobás: Extremal Graph Theory.Academic Press, New York, 1978. MR 0506522 |
| Reference:
|
[5] J. A. Bondy, U. S. R. Murty: Graph Theory with Applications.North Holland, New York, 1976. MR 0411988 |
| Reference:
|
[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. MR 0820842, 10.1016/0012-365X(86)90190-1 |
| Reference:
|
[7] H. Enomoto, Y. Usami: The star arboricity of complete bipartite graphs.Graph Theory, Combinatorics and Applications 1 (1988), 389–396. MR 1170792 |
| Reference:
|
[8] J. Hagauer, S. Klavžar: On independence numbers of the Cartesian product of graphs.ARS Combin. 43 (1996), 149–157. MR 1415983 |
| Reference:
|
[9] S. L. Hakimi, J. Mitchem, E. Schmeichel: Star arboricity of graphs.Discrete Math. 149 (1996), 93–98. MR 1375101, 10.1016/0012-365X(94)00313-8 |
| Reference:
|
[10] P. K. Jha, S. Klavžar: Independence in direct-product graphs.ARS Combin. 50 (1998), 53–63. MR 1670588 |
| Reference:
|
[11] C. Lin, J.-J. Lin, and H.-C. Lee: Some decomposition invariants of crowns.ARS Combin. 66 (2003), 33–48. MR 1961473 |
| Reference:
|
[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 |
| Reference:
|
[13] K.-W. Lih, D.-F. Liu, and X. Zhu: Star extremal circulant graphs.SIAM J. Discrete Math. 12 (1999), 491–499. MR 1720404, 10.1137/S0895480198342838 |
| Reference:
|
[14] C. St. J. A. Nash-Williams: Decomposition of finite graphs into forests.J. London Math. Soc. 39 (1964), 12. Zbl 0119.38805, MR 0161333 |
| Reference:
|
[15] M. Truszczynski: Decomposing graphs into forests of stars.Congr. Numer. 54 (1986), 73–86. Zbl 0646.05022, MR 0885263 |
| . |
