Graph enumeration

The complete list of all free trees on 2,3,4 labeled vertices: 2^{2-2}=1 tree with 2 vertices, 3^{3-2}=3 trees with 3 vertices and 4^{4-2}=16 trees with 4 vertices.

In combinatorics, an area of mathematics, graph enumeration describes a class of combinatorial enumeration problems in which one must count undirected or directed graphs of certain types, typically as a function of the number of vertices of the graph.[1] These problems may be solved either exactly (as an algebraic enumeration problem) or asymptotically. The pioneers in this area of mathematics were Pólya,[2] Cayley [3] and Redfield.[4]

Labeled vs unlabeled problems

In some graphical enumeration problems, the vertices of the graph are considered to be labeled in such a way as to be distinguishable from each other, while in other problems any permutation of the vertices is considered to form the same graph. In general, labeled problems tend to be easier to solve than unlabeled problems.[5] As with combinatorial enumeration more generally, the Pólya enumeration theorem is an important tool for dealing with symmetries such as this.

Exact enumeration formulas

Some important results in this area include the following.

C_n=2^{n\choose 2} - \frac{1}{n}\sum_{k=1}^{n-1} k{n\choose k} 2^{n-k\choose 2} C_k.
from which one may easily calculate, for n = 1, 2, 3, ..., that the values for Cn are
1, 1, 4, 38, 728, 26704, 1866256, ...(sequence A001187 in OEIS)
2^{n-4}+2^{\lfloor (n-4)/2\rfloor}.

References

  1. Harary, Frank; Palmer, Edgar M. (1973). Graphical Enumeration. Academic Press. ISBN 0-12-324245-2.
  2. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 (1937), 145-254
  3. "Cayley, Arthur (CLY838A)". A Cambridge Alumni Database. University of Cambridge.
  4. The theory of group-reduced distributions. American J. Math. 49 (1927), 433-455.
  5. Harary and Palmer, p. 1.
  6. Harary and Palmer, p. 3.
  7. Harary and Palmer, p. 5.
  8. Harary and Palmer, p. 7.
  9. Harary, Frank; Schwenk, Allen J. (1973), "The number of caterpillars", Discrete Mathematics 6 (4): 359–365, doi:10.1016/0012-365x(73)90067-8.


This article is issued from Wikipedia - version of the Sunday, December 27, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.