Arboricity

From Wikipedia, the free encyclopedia

You have new messages (last change).

The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning trees needed to cover all the edges of the graph. The arboricity of a graph can be expressed as a special case of a more general matroid sum problem, in which one wishes to express a set of elements of a matroid as a union of a small number of independent sets. As a consequence, the arboricity can be calculated by a polynomial-time algorithm.

As any n-vertex forest has at most n-1 edges, the arboricity of a graph with n vertices and m edges is at least \lceil m/(n-1)\rceil. Additionally, the subgraphs of any graph cannot have arboricity larger than the graph itself, or equivalently the arboricity of a graph must be at least the maximum arboricity of any of its subgraphs. Nash-Williams proved that these two facts can be combined to characterize arboricity: if we let nS and mS denote the number of vertices and edges, respectively, of any subgraph S of the given graph, then the arboricity of the graph equals \max\{\lceil m_S/(n_S-1)\rceil\}.

Any planar graph with n vertices has at most 3n-6 edges, from which it follows by Nash-Williams' formula that planar graphs have arboricity at most three. Schnyder used a special decomposition of a planar graph into three forests called a Schnyder wood to find a straight-line embedding of any planar graph into a grid of small area.

[edit] Related concepts

  • The star arboricity of a graph is the minimum number of forests, each tree of which is a star (tree with at most one non-leaf node), into which the edges of the graph can be partitioned. If a tree is not a star itself, its star arboricity is two, as can be seen by partitioning the edges into two subsets at odd and even distances from the tree root respectively. Therefore, the star arboricity of any graph is at least equal to the arboricity, and at most equal to twice the arboricity.
  • The linear arboricity of a graph is the minimum number of linear forests (forests in which all vertices are incident to at most two edges) into which the edges of the graph can be partitioned. The linear arboricity of a graph is closely related to its maximum degree.
  • The thickness of a graph is the minimum number of planar subgraphs into which its edges can be partitioned. As any planar graph has arboricity three, the thickness of any graph is at least equal to a third of the arboricity, and at most equal to the arboricity.
  • The degeneracy of a graph is the maximum, over all induced subgraphs of the graph, of the minimum degree of a vertex in the subgraph. The degeneracy of any graph may be computed efficiently by a greedy algorithm that repeatedly deletes the minimum degree vertex of the graph and finds the maximum of the degrees of the deleted vertices. The degeneracy of a graph with arboricity a is at least equal to a, and at most equal to 2a-1.

[edit] References

  • N. Alon (1988). "The linear arboricity of graphs". Israel J. Math. 62: 311–325. 
  • C. St. J. A. Nash-Williams (1961). "Edge-disjoint spanning trees of finite graphs". J. London Math. Soc. 36: 445–450. 
  • C. St. J. A. Nash-Williams (1964). "Decomposition of a finite graph into forests". J. London Math. Soc. 39: 12. 
  • W. T. Tutte (1961). "On the problem of decomposing a graph into n connected factors". J. London Math. Soc. 36: 221–230. 
Retrieved from "http://en.wikipedia.org../../../a/r/b/Arboricity.html"