Regular graph explained

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each internal vertex are equal to each other.^[1] A regular graph with vertices of degree is called a graph or regular graph of degree .

Special cases

Regular graphs of degree at most 2 are easy to classify: a graph consists of disconnected vertices, a graph consists of disconnected edges, and a graph consists of a disjoint union of cycles and infinite chains.

In analogy with the terminology for polynomials of low degrees, a or graph often is called a cubic graph or a quartic graph, respectively. Similarly, it is possible to denote k-regular graphs with

k=5,6,7,8,\ldots

as quintic, sextic, septic, octic, et cetera.

A strongly regular graph is a regular graph where every adjacent pair of vertices has the same number of neighbors in common, and every non-adjacent pair of vertices has the same number of neighbors in common. The smallest graphs that are regular but not strongly regular are the cycle graph and the circulant graph on 6 vertices.

The complete graph is strongly regular for any .

Properties

By the degree sum formula, a -regular graph with vertices has

	nk
	2

edges. In particular, at least one of the order and the degree must be an even number.

A theorem by Nash-Williams says that every graph on vertices has a Hamiltonian cycle.

bf{j}=(1,...,1)

is an eigenvector of A.^[2] Its eigenvalue will be the constant degree of the graph. Eigenvectors corresponding to other eigenvalues are orthogonal to

bf{j}

, so for such eigenvectors

v=(v_1,...,v_n)

, we have

	n
\sum
	i=1

v_i=0

A regular graph of degree k is connected if and only if the eigenvalue k has multiplicity one. The "only if" direction is a consequence of the Perron–Frobenius theorem.^[2]

There is also a criterion for regular and connected graphs :a graph is connected and regular if and only if the matrix of ones J, with

J_ij=1

, is in the adjacency algebra of the graph (meaning it is a linear combination of powers of A).^[3]

Let G be a k-regular graph with diameter D and eigenvalues of adjacency matrix

k=λ₀>λ_1\geq … \geqλ_n-1

. If G is not bipartite, then

D\leq

	log{(n-1)

}+1. ^[4]

Existence

There exists a

-regular graph of order

if and only if the natural numbers and satisfy the inequality

n\geqk+1

and that

is even.

Proof: If a graph with vertices is -regular, then the degree of any vertex v cannot exceed the number

n-1

of vertices different from v, and indeed at least one of and must be even, whence so is their product.

	s_1,\ldots,s_r
C
	n

of order (where the

s_i

denote the minimal `jumps' such that vertices with indices differing by an

s_i

are adjacent). If in addition is even, then

k=2r

, and a possible choice is

(s_1,\ldots,s_r)=(1,2,\ldots,r)

. Else is odd, whence must be even, say with

n=2m

, and then

k=2r-1

and the `jumps' may be chosen as

(s_1,\ldots,s_r)=(1,2,\ldots,r-1,m)

n=k+1

, then this circulant graph is complete.

Generation

Fast algorithms exist to generate, up to isomorphism, all regular graphs with a given degree and number of vertices.^[5]

External links

- - GenReg software and data by Markus Meringer.

Notes and References

Book: Chen, Wai-Kai . Graph Theory and its Engineering Applications . World Scientific . 1997 . 29 . 978-981-02-1859-1 . registration .
Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.
.
10.1006/aima.1994.1052. 0001-8708. 106. 1. 122–148. Quenell. G.. Spectral Diameter Estimates for k-Regular Graphs. Advances in Mathematics. 2025-04-10. 1994-06-01. subscription. https://www.sciencedirect.com/science/article/pii/S0001870884710528
Meringer . Markus . 1999 . Fast generation of regular graphs and construction of cages . . 30 . 2 . 137 - 146 . 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G.