Anarboricity
المؤلف:
Harary, F.
المصدر:
"Covering and Packing in Graphs, I." Ann. New York Acad. Sci. 175
الجزء والصفحة:
...
17-3-2022
2165
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
