Regular graph

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 graph with vertices of degree k is called a kregular graph or regular graph of degree k.

Regular graphs of degree at most 2 are easy to classify: A 0-regular graph consists of disconnected vertices, a 1-regular graph consists of disconnected edges, and a 2-regular graph consists of disconnected cycles.

A 3-regular graph is known as a cubic graph.

A strongly regular graph is a regular graph where every adjacent pair of vertices has the same number "l" of neighbors in common, and every non-adjacent pair of vertices has the same number "n" 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 $K\_m$ is strongly regular for any $m$.

A theorem by Nash-Williams says that every kregular graph on 2k + 1 vertices has a Hamiltonian cycle.

Algebraic properties

Let "A" be the adjacency matrix of the graph. Now the graph is regular if and only if is an eigenvector of "A". When it is an eigenvector, the eigenvalue will be the constant degree of the graph.

When the graph is regular with degree "k", the graph will be connected if and only if "k" has algebraic (and geometric) dimension one.

There is also a criterion for regular and connected graphs :a graph is connected and regular if and only if the matrix "J", with $J\_\{ij\}=1$, is in the adjacency algebra of the graph (meaning it is a linear combination of powers of "A").

See also

* Strongly regular graph

References

*
*
* Citation | last=Nash-Williams | first=Crispin |authorlink = Crispin St. J. A. Nash-Williams
contribution=Valency Sequences which force graphs to have Hamiltonian Circuits
title=University of Waterloo Research Report | publisher=University of Waterloo
place=Waterloo, Ontario | year=1969