Regular graph

(Redirected from Regular graphs)

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 k is called a k‑regular graph or regular graph of degree k.

Graph families defined by their automorphisms
distance-transitive distance-regular strongly regular
symmetric (arc-transitive) t-transitive, t ≥ 2 skew-symmetric
(if connected)
vertex- and edge-transitive
edge-transitive and regular edge-transitive
vertex-transitive regular (if bipartite)
biregular
Cayley graph zero-symmetric asymmetric

Special cases

edit

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.

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 Km is strongly regular for any m.

Existence

edit

The necessary and sufficient conditions for a  -regular graph of order   to exist are that   and that   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   and degree here is  . So  . This is the minimum   for a particular  . Also note that if any regular graph has order   then number of edges are   so   has to be even. In such case it is easy to construct regular graphs by considering appropriate parameters for circulant graphs.

Properties

edit

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

A theorem by Nash-Williams says that every k‑regular graph on 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   is an eigenvector of A.[2] Its eigenvalue will be the constant degree of the graph. Eigenvectors corresponding to other eigenvalues are orthogonal to  , so for such eigenvectors  , we have  .

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  , 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  . If G is not bipartite, then

 [4]

Generation

edit

Fast algorithms exist to generate, up to isomorphism, all regular graphs with a given degree and number of vertices.[5]

See also

edit

References

edit
  1. ^ Chen, Wai-Kai (1997). Graph Theory and its Engineering Applications. World Scientific. pp. 29. ISBN 978-981-02-1859-1.
  2. ^ a b Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.
  3. ^ Curtin, Brian (2005), "Algebraic characterizations of graph regularity conditions", Designs, Codes and Cryptography, 34 (2–3): 241–248, doi:10.1007/s10623-004-4857-4, MR 2128333.
  4. ^ [1][citation needed]
  5. ^ Meringer, Markus (1999). "Fast generation of regular graphs and construction of cages" (PDF). Journal of Graph Theory. 30 (2): 137–146. doi:10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G.
edit