Graph enumeration

From HandWiki
The complete list of all free trees on 2, 3, and 4 labeled vertices: [math]\displaystyle{ 2^{2-2}=1 }[/math] tree with 2 vertices, [math]\displaystyle{ 3^{3-2}=3 }[/math] trees with 3 vertices, and [math]\displaystyle{ 4^{4-2}=16 }[/math] 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.Cite error: Closing </ref> missing for <ref> tag Arthur Cayley[1] and J. Howard Redfield.[2]

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, so the vertices are considered identical or unlabeled. In general, labeled problems tend to be easier.[3] As with combinatorial enumeration more generally, the Pólya enumeration theorem is an important tool for reducing unlabeled problems to labeled ones: each unlabeled class is considered as a symmetry class of labeled objects.

Exact enumeration formulas

Some important results in this area include the following.

  • The number of labeled n-vertex simple undirected graphs is 2n(n −1)/2.[4]
  • The number of labeled n-vertex simple directed graphs is 2n(n −1).[5]
  • The number Cn of connected labeled n-vertex undirected graphs satisfies the recurrence relation[6]
[math]\displaystyle{ 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. }[/math]
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 the OEIS)
[math]\displaystyle{ 2^{n-4}+2^{\lfloor (n-4)/2\rfloor}. }[/math]

Graph database

Various research groups have provided searchable database that lists graphs with certain properties of a small sizes. For example

References

  1. "Cayley, Arthur (CLY838A)". A Cambridge Alumni Database. University of Cambridge. http://venn.lib.cam.ac.uk/cgi-bin/search-2018.pl?sur=&suro=w&fir=&firo=c&cit=&cito=c&c=all&z=all&tex=CLY838A&sye=&eye=&col=all&maxcount=50. 
  2. The theory of group-reduced distributions. American J. Math. 49 (1927), 433-455.
  3. Harary and Palmer, p. 1.
  4. Harary and Palmer, p. 3.
  5. Harary and Palmer, p. 5.
  6. Harary and Palmer, p. 7.
  7. "The number of caterpillars", Discrete Mathematics 6 (4): 359–365, 1973, doi:10.1016/0012-365x(73)90067-8, https://deepblue.lib.umich.edu/bitstream/2027.42/33977/1/0000249.pdf .