Regular graph

From Wikipedia
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

TemplateStyles' src attribute must not be empty.

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

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k=5,6,7,8,\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 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.

Properties

By the degree sum formula, a k-regular graph with n vertices has Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{nk}2} edges. In particular, at least one of the order n and the degree k must be an even number.

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{j}} , so for such eigenvectors Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v=(v_1,\dots,v_n)} , we have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J_{ij}=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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k=\lambda_0 >\lambda_1\geq \cdots\geq\lambda_{n-1}} . If G is not bipartite, then

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D\leq \frac{\log{(n-1)}}{\log(\lambda_0/\lambda_1)}+1. } [4]

Existence

There exists a Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} -regular graph of order Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} if and only if the natural numbers n and k satisfy the inequality Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \geq k+1 } and that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle nk } is even.

Proof: If a graph with n vertices is k-regular, then the degree k of any vertex v cannot exceed the number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} of vertices different from v, and indeed at least one of n and k must be even, whence so is their product.

Conversely, if n and k are two natural numbers satisfying both the inequality and the parity condition, then indeed there is a k-regular circulant graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_n^{s_1,\ldots,s_r}} of order n (where the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_i} denote the minimal `jumps' such that vertices with indices differing by an Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_i} are adjacent). If in addition k is even, then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = 2r} , and a possible choice is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (s_1,\ldots,s_r) = (1,2,\ldots,r)} . Else k is odd, whence n must be even, say with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 2m} , and then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = 2r-1} and the `jumps' may be chosen as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (s_1,\ldots,s_r) = (1,2,\ldots,r-1,m)} .

If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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]

See also

References

  1. ↑ Chen, Wai-Kai (1997). Graph Theory and its Engineering Applications. World Scientific. pp. 29. ISBN 978-981-02-1859-1.
  2. ↑ 2.0 2.1 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. ↑ Quenell, G. (1994-06-01). "Spectral Diameter Estimates for k-Regular Graphs". Advances in Mathematics. 106 (1): 122–148. doi:10.1006/aima.1994.1052. ISSN 0001-8708. Retrieved 2025-04-10.[1]
  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.
Retrieved from "https://wiki.tachyony.co.uk/w/index.php?title=Regular_graph&oldid=74932"