TOPICS
Search

Arboricity

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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)]
(2)

(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)

and of the complete bipartite graph K_(m,n) by

Upsilon(K_(m,n))=[(mn)/(m+n-1)]
(4)

(Harary 1994, p. 91), where [x] is the ceiling function.

See also

Anarboricity, Spanning Tree

Explore with Wolfram|Alpha

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

Arboricity

Cite this as:

Weisstein, Eric W. "Arboricity." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Arboricity.html

Subject classifications