Graph enumeration

From Wikipedia for FEVERv2
Jump to navigation Jump to search

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. Graph enumeration_sentence_0

These problems may be solved either exactly (as an algebraic enumeration problem) or asymptotically. Graph enumeration_sentence_1

The pioneers in this area of mathematics were George Pólya, Arthur Cayley and J. Graph enumeration_sentence_2 Howard Redfield. Graph enumeration_sentence_3

Labeled vs unlabeled problems Graph enumeration_section_0

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. Graph enumeration_sentence_4

In general, labeled problems tend to be easier. Graph enumeration_sentence_5

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. Graph enumeration_sentence_6

Exact enumeration formulas Graph enumeration_section_1

Some important results in this area include the following. Graph enumeration_sentence_7

Graph enumeration_unordered_list_0

  • The number of labeled n-vertex simple undirected graphs is 2.Graph enumeration_item_0_0
  • The number of labeled n-vertex simple directed graphs is 2.Graph enumeration_item_0_1
  • The number Cn of connected labeled n-vertex undirected graphs satisfies the recurrence relationGraph enumeration_item_0_2

Graph enumeration_unordered_list_1

Graph database Graph enumeration_section_2

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

For example Graph enumeration_sentence_9

Graph enumeration_unordered_list_2

  • Graph enumeration_item_2_5
  • Graph enumeration_item_2_6

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: enumeration.