The Star Arboricity of Graphs

I. Algor; N. Alon

doi:10.1016/S0167-5060(08)70561-2

The Star Arboricity of Graphs

I. Algor, N. Alon

Research output: Contribution to journal › Article › peer-review

23 Scopus citations

Abstract

A star forest is a forest whose connected components are stars. The star arboricity st(G) of a graph G is the minimum number of star forests whose union covers all edges of G. We show that for every d-regular graph G, 1/2d < st(G) ≤ 1/4d +O(d 2/3(log d)1/3), and that there are d-regular graphs G with st(G) > 1/2d + Ω(log d). We also observe that the star arboricity of any planar graph is at most 6 and that there are planar graphs whose star arboricity is at least 5.

Original language	English (US)
Pages (from-to)	11-22
Number of pages	12
Journal	Annals of Discrete Mathematics
Volume	43
Issue number	C
DOIs	https://doi.org/10.1016/S0167-5060(08)70561-2
State	Published - Jan 1 1989
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0167-5060(08)70561-2

Cite this

@article{569e14914d484c6ca202db9759dd3e1a,

title = "The Star Arboricity of Graphs",

abstract = "A star forest is a forest whose connected components are stars. The star arboricity st(G) of a graph G is the minimum number of star forests whose union covers all edges of G. We show that for every d-regular graph G, 1/2d < st(G) ≤ 1/4d +O(d 2/3(log d)1/3), and that there are d-regular graphs G with st(G) > 1/2d + Ω(log d). We also observe that the star arboricity of any planar graph is at most 6 and that there are planar graphs whose star arboricity is at least 5.",

author = "I. Algor and N. Alon",

note = "Funding Information: * Research supported in part by Allon Binational Science Foundation. Funding Information: Fellowship and by a grant from the United States Israel",

year = "1989",

month = jan,

day = "1",

doi = "10.1016/S0167-5060(08)70561-2",

language = "English (US)",

volume = "43",

pages = "11--22",

journal = "Annals of Discrete Mathematics",

issn = "0167-5060",

publisher = "Elsevier B.V.",

number = "C",

}

TY - JOUR

T1 - The Star Arboricity of Graphs

AU - Algor, I.

AU - Alon, N.

N1 - Funding Information: * Research supported in part by Allon Binational Science Foundation. Funding Information: Fellowship and by a grant from the United States Israel

PY - 1989/1/1

Y1 - 1989/1/1

N2 - A star forest is a forest whose connected components are stars. The star arboricity st(G) of a graph G is the minimum number of star forests whose union covers all edges of G. We show that for every d-regular graph G, 1/2d < st(G) ≤ 1/4d +O(d 2/3(log d)1/3), and that there are d-regular graphs G with st(G) > 1/2d + Ω(log d). We also observe that the star arboricity of any planar graph is at most 6 and that there are planar graphs whose star arboricity is at least 5.

AB - A star forest is a forest whose connected components are stars. The star arboricity st(G) of a graph G is the minimum number of star forests whose union covers all edges of G. We show that for every d-regular graph G, 1/2d < st(G) ≤ 1/4d +O(d 2/3(log d)1/3), and that there are d-regular graphs G with st(G) > 1/2d + Ω(log d). We also observe that the star arboricity of any planar graph is at most 6 and that there are planar graphs whose star arboricity is at least 5.

UR - https://www.scopus.com/pages/publications/77957079042

UR - https://www.scopus.com/inward/citedby.url?scp=77957079042&partnerID=8YFLogxK

U2 - 10.1016/S0167-5060(08)70561-2

DO - 10.1016/S0167-5060(08)70561-2

M3 - Article

AN - SCOPUS:77957079042

SN - 0167-5060

VL - 43

SP - 11

EP - 22

JO - Annals of Discrete Mathematics

JF - Annals of Discrete Mathematics

IS - C

ER -

The Star Arboricity of Graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this