Regular graph: Difference between revisions

Latest revision as of 03:52, 1 September 2025

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.^[1] 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{n k}{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 $j = (1, \dots, 1)$ is an eigenvector of A.^[2] Its eigenvalue will be the constant degree of the graph. Eigenvectors corresponding to other eigenvalues are orthogonal to $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.^[2]

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_{i j} = 1$ , is in the adjacency algebra of the graph (meaning it is a linear combination of powers of A).^[3]

Let G be a k-regular graph with diameter D and eigenvalues of adjacency matrix $k = λ_{0} > λ_{1} \geq \dots \geq λ_{n - 1}$ . If G is not bipartite, then

D \leq \frac{\log (n - 1)}{\log (λ_{0} / λ_{1})} + 1 .

^[4]

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 \geq k + 1$ and that $n k$ 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 = 2 r$ , 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 = 2 m$ , and then $k = 2 r - 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.^[5]

References

Template:Reflist

External links

Script error: No such module "Template wrapper".
Script error: No such module "Template wrapper".
GenReg software and data by Markus Meringer.
Script error: No such module "citation/CS1".

↑ Script error: No such module "citation/CS1".
↑ ^a ^b Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.
↑ Script error: No such module "citation/CS1"..
↑ Script error: No such module "Citation/CS1".[1]
↑ Script error: No such module "Citation/CS1".

[1] Script error: No such module "citation/CS1".

[Cvetkovic-2] Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.

[3] Script error: No such module "citation/CS1"..

[4] Script error: No such module "Citation/CS1".[1]

[5] Script error: No such module "Citation/CS1".

[1]

[2]

[3]

[4]

[5]

@@ Line 9: / Line 9: @@
 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 graphs|disjoint union]] of [[cycle (graph theory)|cycle]]s and infinite chains.
-A {{nowrap|3-regular}} graph is known as a [[cubic graph]].
+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 <math>k=5,6,7,8,\ldots</math> as quintic, sextic, septic, octic, ''et&nbsp;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.
@@ Line 21: / Line 21: @@
 Image:3-regular_graph.svg|3-regular graph
 </gallery>
-== Existence ==
-The necessary and sufficient conditions for a <math>k</math>-regular graph of [[Glossary of graph theory#order|order]] <math>n</math> to exist are that <math> n \geq k+1 </math> and that <math> nk </math> is even.
-Proof: A [[complete graph]] has every pair of distinct vertices connected to each other by a unique edge. So edges are maximum in complete graph and number of edges are <math>\binom{n}{2} = \dfrac{n(n-1)}{2}</math> and degree here is <math>n-1</math>. So <math>k=n-1,n=k+1</math>. This is the minimum <math>n</math> for a particular <math>k</math>. Also note that if any regular graph has order <math>n</math> then number of edges are <math>\dfrac{nk}{2}</math> so <math>nk</math> has to be even.
-In such case it is easy to construct regular graphs by considering appropriate parameters for [[circulant graph]]s.
 ==Properties==
-From the [[handshaking lemma]], a {{mvar|k}}-regular graph with odd {{mvar|k}} has an even number of vertices.
+By the [[degree sum formula]], a {{mvar|k}}-regular graph with {{mvar|n}} vertices has <math>\frac{nk}2</math> edges. In particular, at least one of the order {{mvar|n}} and the degree {{mvar|k}} must be an even number.
 A theorem by [[Crispin St. J. A. Nash-Williams|Nash-Williams]] says that every {{nowrap|{{mvar|k}}‑regular}} graph on {{math|2''k'' + 1}} vertices has a [[Hamiltonian cycle]].
@@ Line 52: / Line 45: @@
 Let ''G'' be a ''k''-regular graph with diameter ''D'' and eigenvalues of adjacency matrix <math>k=\lambda_0 >\lambda_1\geq \cdots\geq\lambda_{n-1}</math>. If ''G'' is not bipartite, then
-: <math>D\leq \frac{\log{(n-1)}}{\log(\lambda_0/\lambda_1)}+1. </math><ref>{{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 <i>k</i>-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]</ref>
+: <math>D\leq \frac{\log{(n-1)}}{\log(\lambda_0/\lambda_1)}+1. </math><ref>{{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 <i>k</i>-Regular Graphs| journal = Advances in Mathematics| access-date = 2025-04-10| date = 1994-06-01| url = https://www.sciencedirect.com/science/article/pii/S0001870884710528| url-access = subscription}}[https://www.sciencedirect.com/science/article/pii/S0001870884710528]</ref>
+== Existence ==
+There exists a <math>k</math>-regular graph of [[Glossary of graph theory#order|order]] <math>n</math> if and only if the natural numbers {{mvar|n}} and {{mvar|k}} satisfy the inequality <math> n \geq k+1 </math> and that <math> nk </math> 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 <math>n-1</math> 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]] <math>C_n^{s_1,\ldots,s_r}</math> of order {{mvar|n}} (where the <math>s_i</math> denote the minimal `jumps' such that vertices with indices differing by an <math>s_i</math> are adjacent). If in addition {{mvar|k}} is even, then <math>k = 2r</math>, and a possible choice is <math>(s_1,\ldots,s_r) = (1,2,\ldots,r)</math>. Else {{mvar|k}} is odd, whence {{mvar|n}} must be even, say with <math>n = 2m</math>, and then <math>k = 2r-1</math> and the `jumps' may be chosen as <math>(s_1,\ldots,s_r) = (1,2,\ldots,r-1,m)</math>.
+If <math>n=k+1</math>, then this circulant graph is [[complete graph|complete]].
 == Generation ==

Regular graph: Difference between revisions

Latest revision as of 03:52, 1 September 2025

Contents

Special cases

Properties

Existence

Generation

See also

References

External links

Navigation menu

Regular graph: Difference between revisions

Latest revision as of 03:52, 1 September 2025

Special cases

Properties

Existence

Generation

See also

References

External links

Navigation menu

Search