Arboricity
المؤلف:
Harary, F.
المصدر:
"Covering and Packing in Graphs, I." Ann. New York Acad. Sci. 175
الجزء والصفحة:
...
17-3-2022
3218
Arboricity
Given a graph 
, the arboricity 
is the minimum number of edge-disjoint acyclic subgraphs (i.e., spanning forests) whose union is 
.
An acyclic graph therefore has 
.
It appears that a regular graph 
of vertex degree 
has arboricity
 |
(1)
|
Let 
be a nonempty graph on 
vertices and 
edges and let 
be the maximum number of edges in any subgraph of 
having 
vertices. Then
![Upsilon(G)=max_(p>1)[(m_p)/(p-1)]](https://mathworld.wolfram.com/images/equations/Arboricity/NumberedEquation2.svg) |
(2)
|
(Nash-Williams 1961; Harary 1994, p. 90).
The arboricity of a planar graph is at most 3 (Harary 1994, p. 124, Problem 11.22).
The arboricity of the complete graph 
is given by
![Upsilon(K_n)=[n/2]](https://mathworld.wolfram.com/images/equations/Arboricity/NumberedEquation3.svg) |
(3)
|
and of the complete bipartite graph 
by
![Upsilon(K_(m,n))=[(mn)/(m+n-1)]](https://mathworld.wolfram.com/images/equations/Arboricity/NumberedEquation4.svg) |
(4)
|
(Harary 1994, p. 91), where ![[x]](https://mathworld.wolfram.com/images/equations/Arboricity/Inline15.svg)
is the ceiling function.
REFERENCES
Harary, F. "Covering and Packing in Graphs, I." Ann. New York Acad. Sci. 175, 198-205, 1970.
Harary, F. "Arboricity." In Graph Theory. Reading, MA: Addison-Wesley, pp. 90-92, 1994.
Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, p. 225, 1973.
Harary, F. and Palmer, E. M. "A Survey of Graph Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam: North-Holland, pp. 259-275, 1973.
Nash-Williams, C. St. J. A. "Edge-Disjoint Spanning Trees of Finite Graphs." J. London Math. Soc. 36, 455-450, 1961.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
