Regular graph

Revision as of 09:51, 10 April 2025 by imported>Anthony Couthures (Add proper citation to the paper that was missing from I assume personal repo. Redirect to the journal paper + citation.)
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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.<ref> Template:Cite book</ref> A regular graph with vertices of degree Template:Mvar is called a Template:Nowrap graph or regular graph of degree Template:Mvar.

Template:Tocleft

Special casesEdit

Regular graphs of degree at most 2 are easy to classify: a Template:Nowrap graph consists of disconnected vertices, a Template:Nowrap graph consists of disconnected edges, and a Template:Nowrap graph consists of a disjoint union of cycles and infinite chains.

A Template:Nowrap 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 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.

ExistenceEdit

The necessary and sufficient conditions for a <math>k</math>-regular graph of 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 graphs.

PropertiesEdit

From the handshaking lemma, a Template:Mvar-regular graph with odd Template:Mvar has an even number of vertices.

A theorem by Nash-Williams says that every Template:Nowrap 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 <math>\textbf{j}=(1, \dots ,1)</math> is an eigenvector of A.<ref name="Cvetkovic">Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.</ref> Its eigenvalue will be the constant degree of the graph. Eigenvectors corresponding to other eigenvalues are orthogonal to <math>\textbf{j}</math>, so for such eigenvectors <math>v=(v_1,\dots,v_n)</math>, we have <math>\sum_{i=1}^n v_i = 0</math>.

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.<ref name="Cvetkovic"/>

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 <math>J_{ij}=1</math>, is in the adjacency algebra of the graph (meaning it is a linear combination of powers of A).<ref>Template:Citation.</ref>

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>Template:Cite journal[1]</ref>

GenerationEdit

Fast algorithms exist to generate, up to isomorphism, all regular graphs with a given degree and number of vertices.<ref>Template:Cite journal</ref>

See alsoEdit

ReferencesEdit

Template:Reflist

External linksEdit

  • {{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web

|_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:RegularGraph%7CRegularGraph.html}} |title = Regular Graph |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }}

  • {{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web

|_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:StronglyRegularGraph%7CStronglyRegularGraph.html}} |title = Strongly Regular Graph |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }}