Arboricity

 

Given a graph , the arboricity  is the minimum number of edge-disjoint acyclic subgraphs (i.e., spanning forests) whose union is .

An acyclic graph therefore has .

It appears that a regular graph  of vertex degree  has arboricity

(1)

Let  be a nonempty graph on  vertices and  edges and let  be the maximum number of edges in any subgraph of  having  vertices. Then

(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  is given by

(3)

and of the complete bipartite graph  by

(4)

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

---

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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength