Regular graph

Regular graphs of degree at most 2 are easy to classify: a {{nowrap|0-regular}} graph consists of disconnected vertices, a {{nowrap|1-regular}} graph consists of disconnected edges, and a {{nowrap|2-regular}} graph consists of a disjoint union of cycles and infinite chains.

In analogy with the terminology for polynomials of low degrees, a {{nowrap|3-regular}} or {{nowrap|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,\backslash ldots$ 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 {{mvar|l}} of neighbors in common, and every non-adjacent pair of vertices has the same number {{mvar|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 {{mvar|K{{sub|m}}}} is strongly regular for any {{mvar|m}}.

Image:0-regular_graph.svg|0-regular graph

Image:1-regular_graph.svg|1-regular graph

Image:2-regular_graph.svg|2-regular graph

Image:3-regular_graph.svg|3-regular graph

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

A theorem by Nash-Williams says that every {{nowrap|{{mvar|k}}‑regular}} graph on {{math|2k + 1}} vertices has a Hamiltonian cycle.

Let A be the adjacency matrix of a graph. Then the graph is regular if and only if $\backslash textbf\{j\}=(1,\; \backslash dots\; ,1)$ is an eigenvector of A.Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998. Its eigenvalue will be the constant degree of the graph. Eigenvectors corresponding to other eigenvalues are orthogonal to $\backslash textbf\{j\}$, so for such eigenvectors $v=(v\_1,\backslash dots,v\_n)$, we have $\backslash 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).{{citation

| last = Curtin | first = Brian

| doi = 10.1007/s10623-004-4857-4

| issue = 2–3

| journal = Designs, Codes and Cryptography

| mr = 2128333

| pages = 241–248

| title = Algebraic characterizations of graph regularity conditions

| volume = 34

| year = 2005}}.

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

: $D\backslash leq\; \backslash frac\{\backslash log\{(n-1)\}\}\{\backslash log(\backslash lambda\_0/\backslash lambda\_1)\}+1.${{Cite journal| doi = 10.1006/aima.1994.1052| issn = 0001-8708| volume = 106| issue = 1| pages = 122–148| last = Quenell| first = G.| title = Spectral Diameter Estimates for k-Regular Graphs| journal = Advances in Mathematics| access-date = 2025-04-10| date = 1994-06-01| url = https://www.sciencedirect.com/science/article/pii/S0001870884710528}}[https://www.sciencedirect.com/science/article/pii/S0001870884710528]

There exists a $k$-regular graph of order $n$ if and only if the natural numbers {{mvar|n}} and {{mvar|k}} satisfy the inequality $n\; \backslash geq\; k+1$ and that $nk$ is even.

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

Conversely, if {{mvar|n}} and {{mvar|k}} are two natural numbers satisfying both the inequality and the parity condition, then indeed there is a {{mvar|k}}-regular circulant graph $C\_n^\{s\_1,\backslash ldots,s\_r\}$ of order {{mvar|n}} (where the $s\_i$ denote the minimal `jumps' such that vertices with indices differing by an $s\_i$ are adjacent). If in addition {{mvar|k}} is even, then $k\; =\; 2r$, and a possible choice is $(s\_1,\backslash ldots,s\_r)\; =\; (1,2,\backslash ldots,r)$. Else {{mvar|k}} is odd, whence {{mvar|n}} must be even, say with $n\; =\; 2m$, and then $k\; =\; 2r-1$ and the `jumps' may be chosen as $(s\_1,\backslash ldots,s\_r)\; =\; (1,2,\backslash ldots,r-1,m)$.

If $n=k+1$, then this circulant graph is complete.

Fast algorithms exist to generate, up to isomorphism, all regular graphs with a given degree and number of vertices.{{cite journal| last=Meringer | first=Markus | year=1999 | title=Fast generation of regular graphs and construction of cages | journal=Journal of Graph Theory | volume=30 | issue=2 | pages=137–146 | doi= 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G| url=http://www.mathe2.uni-bayreuth.de/markus/pdf/pub/FastGenRegGraphJGT.pdf}}

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

{{reflist}}

• {{MathWorld|urlname=RegularGraph|title=Regular Graph}}
• {{MathWorld|urlname=StronglyRegularGraph|title=Strongly Regular Graph}}
• [http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html GenReg] software and data by Markus Meringer.
• {{Citation | last=Nash-Williams | first=Crispin |author-link = Crispin St. J. A. Nash-Williams

| title=Valency Sequences which force graphs to have Hamiltonian Circuits

| series=University of Waterloo Research Report | publisher=University of Waterloo

| place=Waterloo, Ontario | year=1969 }}

{{DEFAULTSORT:Regular Graph}}

Category:Graph families

*