Regular graph

Template:Short description Template:Refimprove Template:Graph families defined by their automorphisms 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. A regular graph with vertices of degree Template:Mvar is called a Template:Mvar‑regular graph or regular graph of degree Template:Mvar.

Special cases

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 a disjoint union of cycles and infinite chains.

In analogy with the terminology for polynomials of low degrees, a 3-regular or 4-regular 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,\dots$ 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 Template:Mvar of neighbors in common, and every non-adjacent pair of vertices has the same number Template:Mvar 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 Template:Mvar is strongly regular for any Template:Mvar.

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

Properties

By the degree sum formula, a Template:Mvar-regular graph with Template:Mvar vertices has $\frac{nk}{2}$ edges. In particular, at least one of the order Template:Mvar and the degree Template:Mvar must be an even number.

A theorem by Nash-Williams says that every Template:Mvar‑regular graph on Template:Math vertices has a Hamiltonian cycle.

Let A be the adjacency matrix of a graph. Then the graph is regular if and only if $\text{j}=(1,\dots ,1)$ is an eigenvector of A. Its eigenvalue will be the constant degree of the graph. Eigenvectors corresponding to other eigenvalues are orthogonal to $\text{j}$, so for such eigenvectors $v=(v_1,\dots ,v_n)$, we have $\sum _{i=1}^n{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.

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

Let G be a k-regular graph with diameter D and eigenvalues of adjacency matrix $k={\lambda }_0>{\lambda }_1\ge \cdots \ge {\lambda }_{n-1}$. If G is not bipartite, then

$D\le \frac{\log (n-1)}{\log ({\lambda }_0/{\lambda }_1)}+1.$

Existence

There exists a $k$-regular graph of order $n$ if and only if the natural numbers Template:Mvar and Template:Mvar satisfy the inequality $n\ge k+1$ and that $nk$ is even.

Proof: If a graph with Template:Mvar vertices is Template:Mvar-regular, then the degree Template:Mvar of any vertex v cannot exceed the number $n-1$ of vertices different from v, and indeed at least one of Template:Mvar and Template:Mvar must be even, whence so is their product.

Conversely, if Template:Mvar and Template:Mvar are two natural numbers satisfying both the inequality and the parity condition, then indeed there is a Template:Mvar-regular circulant graph $C_n^{s_1,\dots ,s_r}$ of order Template:Mvar (where the $s_i$ denote the minimal `jumps' such that vertices with indices differing by an $s_i$ are adjacent). If in addition Template:Mvar is even, then $k=2r$, and a possible choice is $(s_1,\dots ,s_r)=(1,2,\dots ,r)$. Else Template:Mvar is odd, whence Template:Mvar must be even, say with $n=2m$, and then $k=2r-1$ and the `jumps' may be chosen as $(s_1,\dots ,s_r)=(1,2,\dots ,r-1,m)$.

If $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.

See also

• Random regular graph
• Strongly regular graph
• Moore graph
• Cage graph
• Highly irregular graph

External links

• GenReg software and data by Markus Meringer.