In graph theory , a graph is called regular if all of its nodes have the same number of neighbors, i.e. have the same degree . In the case of a regular directed graph , the stronger condition must apply that all nodes have the same degree of entry and exit . A regular graph with nodes of degree k is called k-regular or regular graph of degree k .
Regular graphs with a degree of at most 2 are easy to classify: a 0-regular graph consists of disconnected nodes, a 1-regular graph consists of disconnected edges, and a 2-regular graph consists of disconnected circles .
A 3-regular graph is also called a cubic graph .
A strongly regular graph is a regular graph in which every 2 neighboring nodes have exactly a common neighbors , and every two non-neighboring nodes have exactly b common neighbors. The smallest regular, but not strongly regular graph is the circle graph and the circular graph with 6 nodes each.
The full graph is strongly regular for each .
According to a Nash-Williams theorem , every k -regular graph with vertices has a Hamilton cycle .
Let A be the adjacency matrix of a graph. The graph is regular if an eigenvector of A is. The eigenvalue of this vector is synonymous with the degree of the graph. Eigenvectors with other eigenvalues are orthogonal to , i.e. H. for such eigenvectors applies: .
A regular graph of degree k is connected if and only if the eigenvalue k has the multiplicity one.
The number of connected -regular graphs increases for a given essentially faster than exponentially with the number of nodes . Obviously, if and are odd, that number is 0.
The following table shows the numbers determined for and using a computer :
|Number of connected regular graphs|
- Eric W. Weisstein : Regular Graph . In: MathWorld (English).
- Eric W. Weisstein : Strongly Regular Graph . In: MathWorld (English).
- GenReg software and data by Markus Meringer.
- ^ Wai-Kai Chen: Graph Theory and its Engineering Applications . World Scientific, 1997, ISBN 978-981-02-1859-1 , pp. 29 .
- ^ A b D. M. Cvetković, M. Doob, H. Sachs: Spectra of Graphs: Theory and Applications . 3rd revised edition. Wiley, New York 1998.
- ↑ sequence A068934 in OEIS
- ^ Wolfram MathWorld: Regular Graph