Arboricity and Star Arboricity of Graphs
Authors:
- Andrzej Kurek
Abstract
The arboricity A(G) of the graph G is the minimum number of forests whose union covers all edges of G. A star forest is a forest in which every connected component is a star. The star arboricity st(G) of a graph G is the minimum number of star forests whose union covers all edges of G. Since every tree can be decomposed into two star forests, st(G)≤2A(G) for every graph G. In [1] the question about the maximum star arboricity of a graph with given arboricity was posed. We show that for any k there exists a graph with A(G) = k and st(G) = 2k. The same result was obtained independently by Alon, McDiarmid and Reed (see [2]). © 1992, Academic Press, Inc. All rights reserved.
- Record ID
- UAM2c7fae45d38c42419845b406287727ef
- Author
- Pages
- 171-173
- Book
- Annals of Discrete Mathematics, Annals of Discrete Mathematics, 1992, 171-173 p.
- ASJC Classification
- DOI
- DOI:10.1016/S0167-5060(08)70624-1 Opening in a new tab
- Language
- (en) English
- Score (nominal)
- 3
- Publication indicators
- = 2; : 2005 = 0.000
- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAM2c7fae45d38c42419845b406287727ef/
- URN
urn:amu-prod:UAM2c7fae45d38c42419845b406287727ef
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.