Arboricity
Given a graph G, the arboricity Upsilon(G) is the minimum number of edge-disjoint acyclic subgraphs (i.e., spanning forests) whose union is G.
An acyclic graph therefore has Upsilon(G)=1.
It appears that a regular graph G of vertex degree d has arboricity
| [画像: Upsilon(G)=|_n/2_|+1. ] |
(1)
|
Let G be a nonempty graph on n vertices and m edges and let m_p be the maximum number of edges in any subgraph of G having p vertices. Then
![画像: Upsilon(G)=max_(p>1)[(m_p)/(p-1)]](/index.cgi/contrast/https://mathworld.wolfram.com/images/equations/Arboricity/NumberedEquation2.svg){kind=link}
(Nash-Williams 1961; Harary 1994, p. 90).
The arboricity of a planar graph is at most 3 (Harary 1994, p. 124, Problem 11.22).
The arboricity of the complete graph K_n is given by
| [画像: Upsilon(K_n)=[n/2] ] |
(3)
|
![画像: Upsilon(K_n)=[n/2]](/index.cgi/contrast/https://mathworld.wolfram.com/images/equations/Arboricity/NumberedEquation3.svg){kind=link}
and of the complete bipartite graph K_(m,n) by
![画像: Upsilon(K_(m,n))=[(mn)/(m+n-1)]](/index.cgi/contrast/https://mathworld.wolfram.com/images/equations/Arboricity/NumberedEquation4.svg){kind=link}
(Harary 1994, p. 91), where [x] is the ceiling function.
See also
Anarboricity, Spanning TreeExplore with Wolfram|Alpha
More things to try:
References
Harary, F. "Covering and Packing in Graphs, I." Ann. New York Acad. Sci. 175, 198-205, 1970.Harary, F. "Arboricity." In Graph Theory. Reading, MA: Addison-Wesley, pp. 90-92, 1994.Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, p. 225, 1973.Harary, F. and Palmer, E. M. "A Survey of Graph Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam: North-Holland, pp. 259-275, 1973.Nash-Williams, C. St. J. A. "Edge-Disjoint Spanning Trees of Finite Graphs." J. London Math. Soc. 36, 455-450, 1961.Referenced on Wolfram|Alpha
ArboricityCite this as:
Weisstein, Eric W. "Arboricity." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Arboricity.html