Regular graph
From Wikipedia, the free encyclopedia
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 Km 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 |
[edit] 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 Jij = 1, is in the adjacency algebra of the graph (meaning it is a linear combination of powers of A).
[edit] See also
[edit] References
- Eric W. Weisstein, Regular Graph at MathWorld.
- Eric W. Weisstein, Strongly Regular Graph at MathWorld.
- Nash-Williams, Crispin (1969), “Valency Sequences which force graphs to have Hamiltonian Circuits”, University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo
