Community hub
0 subscribers7 pages, 0 posts
Recent from talks
All channels
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to Regular graph.
Nothing was collected or created yet.
Regular graph
View on Wikipediafrom Wikipedia
 | This article needs additional citations for verification. (November 2022) |
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
[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.
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 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.
-
0-regular graph -
1-regular graph -
2-regular graph -
3-regular graph
Properties
[edit]By the degree sum formula, a k-regular graph with n vertices has 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 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
Existence
[edit]There exists a -regular graph of order if and only if the natural numbers n and k satisfy the inequality and that is even.
Proof: If a graph with n vertices is k-regular, then the degree k of any vertex v cannot exceed the number 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 of order n (where the denote the minimal `jumps' such that vertices with indices differing by an are adjacent). If in addition k is even, then , and a possible choice is . Else k is odd, whence n must be even, say with , and then and the `jumps' may be chosen as .
If , then this circulant graph is complete.
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]- ^ Chen, Wai-Kai (1997). Graph Theory and its Engineering Applications. World Scientific. pp. 29. ISBN 978-981-02-1859-1.
- ^ a b Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.
- ^ 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.
- ^ 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]
- ^ 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.
External links
[edit]- Weisstein, Eric W. "Regular Graph". MathWorld.
- Weisstein, Eric W. "Strongly Regular Graph". MathWorld.
- GenReg software and data by Markus Meringer.
- Nash-Williams, Crispin (1969), Valency Sequences which force graphs to have Hamiltonian Circuits, University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo
Regular graph
View on Grokipediafrom Grokipedia
In graph theory, a regular graph is a graph in which every vertex has the same degree, meaning each vertex is incident to the same number of edges.[1] This common degree is denoted by , and the graph is then called a -regular graph.[2]
The number of edges in a -regular graph with vertices is , as derived from the handshaking lemma applied uniformly across all vertices.[1] For such a graph to exist, must hold, and must be even, ensuring the total degree sum is even and compatible with the lemma.[2] Their uniform degree structure facilitates their use in studying structural properties like connectivity, matchings, and colorings; for instance, every -regular bipartite graph with has a perfect matching by Hall's marriage theorem.[1]
Common examples include the complete graph , which is -regular, and the empty graph on vertices, which is 0-regular.[1] The cycle graph for is 2-regular, and the complete bipartite graph is -regular.[2] Regular graphs are foundational in areas such as random graph theory, where models of random -regular graphs analyze properties like Hamilton cycles and spanning subgraphs with high probability.[3] They also appear in applications to computer science for modeling symmetric networks and in combinatorial designs for constructing balanced structures.[3]
Definition and Fundamentals
Definition
A regular graph is an undirected graph in which every vertex has the same degree , and such a graph is denoted as -regular.[4][5] This uniformity of degree distinguishes regular graphs from irregular graphs, where vertices may have varying degrees.[4] The concept applies to both simple graphs, which contain no loops or multiple edges between the same pair of vertices, and multigraphs, which permit loops and multiple edges; however, definitions in graph theory often assume simple graphs unless specified otherwise.[5] The term "regular graph" was introduced by Julius Petersen in his 1879 paper "Die Theorie der regulären Graphs".[6] The concept was further developed in the early 20th century, notably through the work of Hungarian mathematician Dénes König, who employed it in his 1916 proofs on bipartite regular graphs and formalized it in his seminal 1936 textbook, Theory of Finite and Infinite Graphs, the first comprehensive book on the subject.[7][8] A representative example of a -regular graph is the complete graph , which has vertices where each connects to every other, achieving degree and representing the smallest such graph on that number of vertices.[9] While regular graphs can be infinite, with every vertex maintaining degree across an unbounded structure, the focus in classical graph theory remains on finite regular graphs.[5]Basic Terminology
A regular graph is denoted by , where is the vertex set and is the edge set, with every vertex having degree , for some fixed integer .[5] Such a graph is called a -regular graph on vertices, or simply .[5] The order of a regular graph is the number of vertices .[5] The size of is the number of edges ; for a -regular simple graph, the handshaking lemma implies .[5] The girth of is the length of its shortest cycle, or infinite if is acyclic.[5] The diameter of a connected graph is the maximum distance between any two vertices.[5] A strongly regular graph is a regular graph with additional constraints on the number of common neighbors for adjacent and non-adjacent vertex pairs.[10] A biregular graph is a bipartite graph in which all vertices in one part have degree and all in the other have degree .[11] Throughout this article, regular graphs are assumed to be undirected and simple unless otherwise specified; in multigraphs, loops contribute 2 to the degree of their incident vertex.[5]Properties
Combinatorial Properties
A fundamental combinatorial property of regular graphs follows from the handshaking lemma. In a -regular graph with vertices, the sum of all vertex degrees is , which equals twice the number of edges , yielding . Consequently, must be even for to be an integer, implying that either or is even.[12] The uniformity of degrees in regular graphs also implies strong connectivity guarantees. Moreover, such graphs are -edge-connected, requiring the removal of at least edges to disconnect them.[13] Regular graphs exhibit notable isoperimetric properties, particularly in bounding edge cuts and expansion. The isoperimetric number of a -regular graph on vertices is defined as measuring the minimum edge expansion relative to subset size.[14] Such bounds are central to expander graphs, where high ensures strong connectivity despite low density.[14] Counting walks in regular graphs leverages their degree homogeneity combinatorially. In a -regular graph with vertices, the total number of walks of length (allowing vertex and edge revisits) is exactly , as each of the starting vertices admits choices at each of the steps.[15] The number of walks of length from a fixed vertex to is given by the -entry of the th power of the adjacency matrix , denoted , and the total closed walks of length equals . Eigenvalues influence these counts, but the combinatorial total holds independently.[15] Eulerian properties provide another key combinatorial insight. A connected -regular graph admits an Eulerian circuit—a closed trail traversing each edge exactly once—if and only if is even, since all degrees are then even. For odd , no such circuit exists in simple graphs, but allowing multiple edges (as in multigraphs) permits Eulerian circuits under connectivity. This follows from Euler's theorem, which equates Eulerian circuits with even degrees in connected graphs.Algebraic Properties
The adjacency matrix of a -regular graph on vertices is a symmetric matrix with zero diagonal entries and exactly ones in each row and column, reflecting the regularity of the graph. As a result, the all-ones vector serves as an eigenvector corresponding to the largest eigenvalue . For connected -regular graphs, this eigenvalue has algebraic multiplicity one.[16] The spectral gap of a connected -regular graph is given by , where is the second-largest eigenvalue of . This gap quantifies the graph's expansion properties, providing upper bounds on the Cheeger constant, and also determines the mixing time of the associated random walk, which is . Larger gaps correspond to stronger expanders with faster convergence to the stationary distribution.[17] For a -regular graph, the (unnormalized) Laplacian matrix is , where is the identity matrix. The eigenvalues of are for , lying in the interval , with having multiplicity one if the graph is connected. The second-smallest eigenvalue (algebraic connectivity) further bounds expansion and connectivity.[18] The trace of the -th power of the adjacency matrix, , equals the total number of closed walks of length in the graph. This relation links the spectrum to combinatorial walk counts, enabling spectral methods to analyze walk distributions in regular graphs. A -regular graph is Ramanujan if every non-trivial eigenvalue (for ) satisfies , achieving the optimal spectral gap conjectured by Alon and proven nearly tight by Friedman for random -regular graphs on sufficiently large , where with high probability.Special Cases
Low-Degree Regular Graphs
A 0-regular graph consists solely of isolated vertices with no edges connecting them, forming what is known as the empty graph on a given number of vertices.[4] This structure is the simplest case of a regular graph, where every vertex has degree zero, and it exists for any finite number of vertices. A 1-regular graph is a disjoint union of edges, where each component is a single edge connecting exactly two vertices, and every vertex has degree one.[4] Such graphs exist only when the total number of vertices is even, as the handshaking lemma requires the sum of degrees to be even, pairing all vertices perfectly in a matching. This configuration is equivalent to a perfect matching spanning the vertex set, with no isolated vertices or larger components.[19] In contrast, a 2-regular graph comprises one or more disjoint cycles, where every vertex has exactly two neighbors, forming closed loops without branches.[4] These graphs exist for any number of vertices greater than or equal to 3, by partitioning the vertices into cycles of lengths at least 3. When connected, a 2-regular graph is precisely the cycle graph for , a fundamental structure in graph theory that models circular arrangements.[20] 3-regular graphs, also called cubic graphs, are more complex, with each vertex incident to exactly three edges, requiring an even number of vertices for existence by the handshaking lemma. A seminal result is Petersen's theorem, which states that every bridgeless 3-regular graph contains a perfect matching.[21] This theorem, originally proved in 1891, guarantees a 1-factor in such graphs without bridges, highlighting their decomposability properties.[22] However, not all 3-regular graphs are Hamiltonian; the Petersen graph on 10 vertices serves as the smallest counterexample, being non-Hamiltonian despite its symmetry and connectivity.[23] For planarity in 3-regular graphs, Euler's formula imposes strict bounds related to girth, the length of the shortest cycle. In a simple planar graph with girth , the number of edges satisfies .[24] For 3-regular graphs, where , this implies that planar realizations cannot have girth 6 or higher, as substituting yields , simplifying to a contradiction . Graphs with girth 5, such as the dodecahedral graph on 20 vertices, achieve the bound near equality and are planar, while those with girth 4 may be non-planar, as exemplified by the utility graph , a 3-regular bipartite graph on 6 vertices that contains no odd cycles but violates planarity by Kuratowski's theorem.Highly Symmetric Regular Graphs
Complete graphs are the paradigmatic example of highly symmetric regular graphs, being -regular on vertices where every pair of distinct vertices is adjacent.[25] These graphs achieve the maximum possible degree for a simple graph on vertices, making them uniquely maximal among regular graphs of their order.[26] Their vertex-transitivity and edge-transitivity underscore their extreme symmetry, with the automorphism group isomorphic to the symmetric group . Cycle graphs provide a foundational instance of 2-regular symmetric graphs, consisting of vertices connected in a single cycle, which is inherently Hamiltonian as the graph itself forms a spanning cycle.[27] For , is vertex-transitive and edge-transitive, serving as a basic building block for more complex symmetric structures due to its uniform degree and cyclic symmetry.[28] Cage graphs represent extremal regular graphs achieving the minimal order for a given degree and girth , defined as the smallest -regular graph with no cycles shorter than .[29] The Petersen graph exemplifies this as the unique (3,5)-cage, a 3-regular graph on 10 vertices with girth 5, renowned for its symmetry and role as a Moore graph of diameter 2.[30] Strongly regular graphs form a broad class of highly symmetric regular graphs characterized by parameters , where the graph has vertices, is -regular, every pair of adjacent vertices shares common neighbors, and every pair of non-adjacent vertices shares common neighbors.[31] These parameters enforce a refined intersection property that enhances symmetry, often leading to distance-regularity. The Hoffman-Singleton graph illustrates this as the unique strongly regular graph with parameters (50, 7, 0, 1), a 7-regular graph on 50 vertices that is also a (7,5)-cage and Moore graph of diameter 2.[32] Moore graphs, which attain the Moore bound for the maximum number of vertices in a -regular graph of diameter 2, are among the most symmetric regular graphs, coinciding with cages for girth 5 in known cases. Known examples include the Petersen graph for , the Hoffman-Singleton graph for , and the cycle graph for ; a possible 57-regular Moore graph on 3250 vertices remains an open question, with its existence undecided despite extensive scrutiny.[33]Existence and Constructions
Existence Conditions
A fundamental necessary condition for the existence of a -regular graph on vertices is that must be even, as the sum of degrees in any graph is twice the number of edges by the handshaking lemma.[34] This parity requirement follows directly from the fact that the total degree sum equals $2|E||E|nkkn$ are odd—no such graph can exist, as it would violate this basic combinatorial constraint.[35] For sufficient conditions, a -regular simple graph on vertices exists whenever , is even, and for . This holds for the complete graph when , disjoint edges when (requiring even), and more generally for intermediate degrees via inductive constructions or random methods. Specifically, for connected -regular graphs with and , existence is guaranteed if is even; if is odd, a connected nearly -regular graph (with degrees or ) exists instead.[36] Non-existence cases beyond the parity condition include the impossibility of a -regular bipartite graph on an odd number of vertices for , as the partite sets must be of equal size to balance the degrees, requiring even . Additionally, bipartite regular graphs cannot have odd girth, since they contain no odd cycles by definition. For , while 2-regular graphs (disjoint cycles) exist on odd via an odd cycle, connected 2-regular bipartite graphs require even for the same bipartition reason. The Erdős–Ginzburg–Ziv theorem, which states that any sequence of integers contains a subsequence of elements summing to a multiple of , has implications for graph decompositions involving regular subgraphs. It aids in proving the existence of regular factors or cycle decompositions in certain dense or regular host graphs, such as ensuring zero-sum properties in edge labelings that correspond to balanced substructures.[37] Petersen's theorem provides a key existence result for 3-regular (cubic) graphs: every bridgeless 3-regular graph on an even number of vertices contains a perfect matching (1-factor). This guarantees the decomposability of such graphs into edge-disjoint matchings under the bridgeless condition, with and even for basic existence.[38] Asymptotically, the configuration model ensures the existence of -regular simple graphs for fixed and large with even. In this model, pairing stubs randomly yields a multigraph, which is simple (no loops or multiple edges) with probability approaching 1 as , thus confirming existence via positive probability.[39]Construction Methods
One prominent method for constructing regular graphs is the configuration model, introduced by Bollobás in 1980. This approach generates a random -regular multigraph on vertices (where is even) by creating stubs (half-edges), one for each endpoint of the edges incident to each vertex, and then performing a random perfect matching on these stubs to form edges. The resulting multigraph may contain self-loops and multiple edges between the same pair of vertices; to obtain a simple graph, these can be resolved by rejection sampling or conditioning on the absence of such features, though the probability of multiples decreases as grows relative to .[40] Another constructive technique adapts the Havel-Hakimi algorithm, originally developed for realizing arbitrary graphical degree sequences, to the uniform case of regular degrees. For a -regular graph on vertices, the algorithm iteratively connects the highest-degree remaining vertex to the highest-degree vertices in the residual sequence, subtracts one from their degrees, removes the connected vertex, and repeats until the sequence is exhausted or a contradiction arises; since the regular sequence is graphical under the evenness condition, this yields a simple -regular graph. This method is deterministic and guarantees connectivity if started appropriately, though it may produce specific realizations rather than uniform random ones. Cayley graphs provide an explicit algebraic construction of regular graphs, defined on the elements of a group with a symmetric generating set excluding the identity, where vertices are group elements and edges connect to for each . The resulting graph is -regular and vertex-transitive. A canonical example is the -dimensional hypercube, which is the Cayley graph of the elementary abelian group generated by the standard basis vectors, yielding an -regular graph on vertices with high symmetry and applications in parallel computing. The switching method, developed by McKay and Wormald, starts from an initial -regular multigraph and iteratively applies local switches to eliminate multiple edges and loops while preserving degrees. Specifically, for non-adjacent edges and forming a multiple or loop, replace them with and (or and ) if the new edges do not already exist, repeating until a simple graph is obtained; this process is Markovian and can be tuned for uniform sampling over isomorphism classes. It is particularly efficient for moderate and , enabling rapid generation of random regular graphs.[41] In practice, software libraries facilitate these constructions. The Python package NetworkX implements the configuration model via itsrandom_regular_graph function to generate random -regular simple graphs on vertices, handling multiplicity resolution internally. Similarly, the nauty suite's geng tool can enumerate or sample all non-isomorphic -regular graphs up to small (e.g., for ), using canonical labeling for efficiency.[42][43]