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 k‑regular 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 k‑regular graph on 2k + 1 vertices has a Hamiltonian cycle.

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

Algebraic properties

Let A be the adjacency matrix of the graph. Now the graph is regular if and only if ${\begin{bmatrix}1\\\vdots \\1\end{bmatrix}}$ 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).

Generation

Regular graphs may be generated by GenReg program.

See also

• Strongly regular graph

References

• Weisstein, Eric W. "Regular Graph". MathWorld.
• Weisstein, Eric W. "Strongly Regular Graph". MathWorld.
• Nash-Williams, Crispin (1969), "Valency Sequences which force graphs to have Hamiltonian Circuits", University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo