Download Wolfram Notebook

The arboricity of a finite simple graph is the minimum number of edge-disjoint acyclic subgraphs (i.e., spanning forests) whose edge sets partition the edge set of . It is the covering version of the packing invariant anarboricity (Harary and Palmer 1973a, p. 225). An edgeless graph has arboricity 0. For with at least two vertices, Nash-Williams (1964) showed that

where is the edge count, is the vertex count of a subgraph , and is the ceiling function.

Writing for the maximum average degree and for the pseudoarboricity, a lower bound is

The pseudoarboricity is the minimum number of pseudoforests whose edge sets partition the edge set of ; each connected component of a pseudoforest has at most one cycle. In general, . For example, the lower bound is attained by every forest and every complete graph of even vertex count. For a cycle graph with , while , so connectedness alone does not imply equality.

For a graph with at least two vertices,

where is the edge count and is the vertex count (Nash-Williams 1964).

This bound immediately gives a number of useful lower bounds. If is the graph degeneracy of , then , so

This bound is often very quick to evaluate, although it need not be sharp. A stronger lower bound is obtained by repeatedly deleting a vertex of minimum vertex degree and considering the resulting chain of residual subgraphs

Then

is also a lower bound for the arboricity, since each is a subgraph of . This peeling bound is always at least as large as , but it is not exact in general, because a densest witness subgraph need not occur along a single minimum vertex degree peeling chain. For example, the bishop graph on a board has peeling bound 3 but arboricity 4, the bishop graph on an board has peeling bound 5 but arboricity 6, and the camel graph on a board has peeling bound 2 but arboricity 3.

An acyclic graph with at least one graph edge therefore has . Furthermore, the arboricity of a planar graph is at most 3 (Harary 1994, p. 124, Problem 11.22).

For a graph on vertices, let be the maximum edge count of a subgraph with vertices. Then

(Nash-Williams 1964; Harary 1994, p. 90).

The arboricity of the complete graph , for , is given by

of the complete bipartite graph , for positive integers and , by

(Harary 1994, p. 91), and of the complete tripartite graph , for positive integers , , and , by

For positive integers , , ..., with , the arboricity of the complete multipartite graph is

Equivalently, writing for the vertex count,

Related parameters change either the permitted edge parts or the set being partitioned. The following table summarizes the variants and the related packing parameter covered here.

See also

Anarboricity, Fractional Arboricity, Linear Arboricity, Maximum Average Degree, Pseudoarboricity, Spanning Tree, Star Arboricity, Vertex Arboricity

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, 1973a.Harary, F. and Palmer, E. M. "A Survey of Graphical Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam, Netherlands: North-Holland, pp. 259-275, 1973b.Nash-Williams, C. St. J. A. "Edge-Disjoint Spanning Trees of Finite Graphs." J. London Math. Soc. 36, 445-450, 1961. https://doi.org/10.1112/jlms/s1-36.1.445.Nash-Williams, C. St. J. A. "Decomposition of Finite Graphs into Forests." J. London Math. Soc. 39, 12, 1964. https://doi.org/10.1112/jlms/s1-39.1.12.

Referenced on Wolfram|Alpha

Arboricity

Cite this as:

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

Subject classifications