TOPICS
Search

Anarboricity


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

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. 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

Anarboricity

Cite this as:

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

Subject classifications