Regular graph

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 . ${\ displaystyle K_ {m}}$ ${\ displaystyle m}$

According to a Nash-Williams theorem , every k -regular graph with vertices has a Hamilton cycle . ${\ displaystyle 2k + 1}$

0-regular graph
1-regular graph
2-regular graph
3-regular graph

Algebraic properties

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: . ${\ displaystyle {\ textbf {j}} = (1, \ dots, 1)}$ ${\ displaystyle {\ textbf {j}}}$ ${\ displaystyle v = (v_ {1}, \ dots, v_ {n})}$ ${\ displaystyle \ textstyle \ sum _ {i = 1} ^ {n} v_ {i} = 0}$

A regular graph of degree k is connected if and only if the eigenvalue k has the multiplicity one.

Combinatorics

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. ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle k}$

The following table shows the numbers determined for and using a computer : ${\ displaystyle n \ leq 16}$ ${\ displaystyle k \ leq 12}$

Number of connected regular graphs
n	k
n	3	4th	5	6th	7th	8th	9	10	11	12
4th	1	0	0	0	0	0	0	0	0	0
5	0	1	0	0	0	0	0	0	0	0
6th	2	1	1	0	0	0	0	0	0	0
7th	0	2	0	1	0	0	0	0	0	0
8th	5	6th	3	1	1	0	0	0	0	0
9	0	16	0	4th	0	1	0	0	0	0
10	19th	59	60	21st	5	1	1	0	0	0
11	0	265	0	266	0	6th	0	1	0	0
12	85	1544	7848	7849	1547	94	9	1	1	0
13	0	10778	0	367860	0	10786	0	10	0	1
14th	509	88168	3459383	21609300	21609301	3459386	88193	540	13	1
15th	0	805491	0	1470293675	0	1470293676	0	805579	0	17th
16	4060	8037418	2585136675	113314233808	733351105934	733351105935	113314233813	2585136741	8037796	4207

Web links

Commons : Regular Graphs - collection of images, videos and audio files

Eric W. Weisstein : Regular Graph . In: MathWorld (English).
Eric W. Weisstein : Strongly Regular Graph . In: MathWorld (English).
GenReg software and data by Markus Meringer.

Individual evidence

^ 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

[1] Wai-Kai Chen: Graph Theory and its Engineering Applications . World Scientific, 1997, ISBN 978-981-02-1859-1 , pp. 29 .

[Cvetkovic-2] A ^b D. M. Cvetković, M. Doob, H. Sachs: Spectra of Graphs: Theory and Applications . 3rd revised edition. Wiley, New York 1998.

[3] sequence A068934 in OEIS

[4] Wolfram MathWorld: Regular Graph