The anarboricity of a graph is the maximum number of edge-disjoint nonacyclic (i.e., cyclic) subgraphs of whose union is (Harary and Palmer 1973a, p. 225). It is the packing version of the covering invariant arboricity (Harary and Palmer 1973a, p. 225). For example, in the graph, a maximum of two edge-disjoint cycles cover the graph as illustrated above, making its anarboricity 2.

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

Anarboricity is defined only for cyclic graphs but may be assigned a value 0 for acyclic 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).

Bridges and leaves do not contribute to anarboricity since, given a valid decomposition of the cyclic core, bridges and pendant edges can be assigned to any one of the constituent cyclic subgraphs. As a result, the anarboricity of a general cyclic graph is equal to the anarboricity of its 2-edge-connected core. Moreover, the anarboricity of a graph is equal to the sum of anarboricities of its blocks.

The anarboricity satisfies

for a graph with edge count since every nonacyclic subgraph contains at least one cycle, the shortest possible cycle has 3 edges, and subgraphs must be edge-disjoint. This bound is tight for odd complete graphs with . For even , choosing one cycle from each nonacyclic subgraph gives edge-disjoint cycles whose union has even degree at every vertex, so at least edges of lie outside these chosen cycles. Therefore,

The edge-count bound is also tight for any graph that admits a decomposition into edge-disjoint triangles, such as the triangular grid graph.

By construction, the Dutch windmill graph has anarboricity , and the special case of the butterfly graph has anarboricity 2.

The wheel graph has anarboricity

as can be seen from the illustrations above.

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. Graphical Enumeration. New York: Academic Press, p. 225, 1973a.Harary, F. and Palmer, E. M. Ch. 21, §P4.8 in "A Survey of Graphical Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam, Netherlands: North-Holland, p. 268, 1973b.

Referenced on Wolfram|Alpha

Anarboricity

Cite this as:

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

Subject classifications