R. C. Read defined the anarboricity of a graph G as the maximum number of edge-disjoint nonacyclic (i.e., cyclic) subgraphs of G whose union is G (Harary and Palmer 1973, p. 268).

Anarboricity is therefore defined only for cyclic graphs. It equals 1 for a unicyclic graph (since the only cyclic subgraph from which the original graph can be constructed is the entire graph).

By construction, the Dutch windmill graph D_n^((m)) has anarboricity m, and the special case of the butterfly graph D_3^((2)) has anarboricity 2.

The term "anarboricity" is a "glorious groaning pun" (in the words of Harary and Palmer 1973, p. 268) on the city of Ann Arbor (the location of the main campus of the University of Michigan).

See also


Explore with Wolfram|Alpha


Harary, F. "Covering and Packing in Graphs, I." Ann. New York Acad. Sci. 175, 198-205, 1970.Harary, F. and Palmer, E. M. Ch. 21, §P4.8 in "A Survey of Graph Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam: North-Holland, p. 268, 1973.Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, p. 225, 1973.

Referenced on Wolfram|Alpha


Cite this as:

Weisstein, Eric W. "Anarboricity." From MathWorld--A Wolfram Web Resource.

Subject classifications