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.

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

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