Graph enumeration

Last updated October 21, 2022

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 George Pólya,^[2] Arthur Cayley ^[3] and J. Howard 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, so the vertices are considered identical or unlabeled. In general, labeled problems tend to be easier.^[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.

Exact enumeration formulas

Some important results in this area include the following.

The number of labeled n-vertex simple undirected graphs is 2^{n(n −1)/2}.^[6]
The number of labeled n-vertex simple directed graphs is 2^n(n −1).^[7]
The number C_n of connected labeled n-vertex undirected graphs satisfies the recurrence relation ^[8]

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 C_n are

1, 1, 4, 38, 728, 26704, 1866256, ...(sequence A001187 in the OEIS )

The number of labeled n-vertex free trees is nⁿ⁻² (Cayley's formula).
The number of unlabeled n-vertex caterpillars is^[9]

2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.

Graph database

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

Related Research Articles

<span class="mw-page-title-main">Graph theory</span> Area of discrete mathematics

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

<span class="mw-page-title-main">Directed acyclic graph</span> Directed graph with no directed cycles

In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology to information science to computation (scheduling).

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. Determining whether such paths and cycles exist in graphs are NP-complete.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Graph (discrete mathematics)</span> Vertices connected in pairs by edges

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem, and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing families of expander graphs.

<span class="mw-page-title-main">Vertex (graph theory)</span> Fundamental unit of which graphs are formed

In mathematics, and more specifically in graph theory, a vertex or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges, while a directed graph consists of a set of vertices and a set of arcs. In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another.

In the mathematical discipline of graph theory, the line graph of an undirected graph $G$ is another graph $L(G)$ that represents the adjacencies between edges of $G$ . $L(G)$ is constructed in the following way: for each edge in $G$ , make a vertex in $L(G)$ ; for every two edges in $G$ that have a vertex in common, make an edge between their corresponding vertices in $L(G)$ .

In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that for every positive integer $, the number of trees on labeled vertices is .$

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graph $Q n$ is the graph formed from the vertices and edges of an $n$ -dimensional hypercube. For instance, the cube graph $Q 3$ is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. $Q n$ has $2 n$ vertices, $2 n - 1 n$ edges, and is a regular graph with $n$ edges touching each vertex.

<span class="mw-page-title-main">Pseudoforest</span> Graph with one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

In mathematics, and more specifically in graph theory, a directed graph is a graph that is made up of a set of vertices connected by directed edges, often called arcs.

In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs. In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected.

In graph theory, a caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path.

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

In graph theory, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph.

<span class="mw-page-title-main">Radio coloring</span>

In graph theory, a branch of mathematics, a radio coloring of an undirected graph is a form of graph coloring in which one assigns positive integer labels to the graphs such that the labels of adjacent vertices differ by at least two, and the labels of vertices at distance two from each other differ by at least one. Radio coloring was first studied by Griggs & Yeh (1992), under a different name, $L (2,1)$ -labeling. It was called radio coloring by Frank Harary because it models the problem of channel assignment in radio broadcasting, while avoiding electromagnetic interference between radio stations that are near each other both in the graph and in their assigned channel frequencies.

References

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[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" (PDF), Discrete Mathematics, 6 (4): 359–365, doi:10.1016/0012-365x(73)90067-8, hdl: 2027.42/33977 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]