The star arboricity of graphs (Q1825208)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The star arboricity of graphs |
scientific article |
Statements
The star arboricity of graphs (English)
0 references
1989
0 references
The star arboricity st(G) of a graph G is the minimum number of star forests the union of which covers all edges of G. (A star forest is a graph every component of which is a star.) For a d-regular graph G an upper and lower bound of st(G) are given: \[ 1/2d\leq st(G)\leq 1/2d+O(d^{2/3}(\log d)^{1/3}). \] The number \(1/2d+\Omega (\log d)\) is not an upper bound of st(G). Finally, for a planar graph G, st(G) is at most 6 and there are planar graphs G with st(G) at least 5.
0 references
algorithm
0 references
probability space
0 references
star arboricity
0 references
d-regular graph
0 references