Added to Favorites

Popular Searches

Nearby Words

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`.## Algebraic properties

## See also

## References

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 2`k` + 1 vertices has a Hamiltonian cycle.

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).

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday June 01, 2008 at 02:55:26 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday June 01, 2008 at 02:55:26 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.