Anarboricity

R. C. Read defined the anarboricity of a graph  as the maximum number of edge-disjoint nonacyclic (i.e., cyclic) subgraphs of  whose union is  (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  has anarboricity , and the special case of the butterfly graph  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).

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.