Regular Graph
A simple graph is said to be regular of degree r if all vertex degrees are the same number r. A 0-regular graph is an empty graph, a 1-regular graph consists of disconnected edges, and a two-regular graph consists of one or more (disconnected) cycles. The first interesting case is therefore 3-regular graphs, which are called cubic graphs (Harary 1994, pp. 14-15). Most commonly, "cubic graphs" is used to mean "connected cubic graphs." Note that n-arc-transitive graphs are sometimes also called "n-regular" (Harary 1994, p. 174).
A directed graph is called regular if the number of edges incident on each vertex is the same, regardless if the edges are in-edges, out-edges, or both. For example, the de Bruijn and Kautz graphs, illustrated above, are directed regular graphs.
A simple graph on an odd number of vertices such that degree of every vertex is the same odd number delta except for a single vertex whose degree is delta+1 may be called a quasi-regular graph (Bozóki et al. 2020).
A semirandom (k,n)-regular graph can be generated using RegularGraph [k, n] in the Wolfram Language package Combinatorica` .
The following table lists the names of low-order d-regular graphs.
Some regular simple graphs of degree higher than 5 are summarized in the following table.
The numbers of nonisomorphic connected regular graphs of order n=1, 2, ... are 1, 1, 1, 2, 2, 5, 4, 17, 22, 167, ... (OEIS A005177; Steinbach 1990).
For an r-regular simple graph on n nodes,
| m=1/2nr, |
where m is the edge count. Let N(n,r) be the number of connected r-regular graphs with n points. Then 0<=r<=n-1, N(n,r)=N(n,n-1-r), and N(n,r)=0 when both n and r are odd. Zhang and Yang (1989) give N(p,r) for p<=12, and Meringer provides a similar tabulation including complete enumerations for low orders.
The following table gives the numbers N(n,r) of connected r-regular simple graphs for small numbers of nodes n (Meringer 1999, Meringer).
Typically, only numbers of connected r-regular graphs on n vertices are published for r<n/2 as a result of the fact that all other numbers can be derived via simple combinatorics using the following facts:
1. Numbers of not-necessarily-connected r-regular graphs on n vertices can be obtained from numbers of connected r-regular graphs on m<=n vertices.
2. Numbers of not-necessarily-connected r-regular graphs on n vertices equal the number of not-necessarily-connected (n-r-1)-regular graphs on n vertices (since building complementary graphs defines a bijection between the two sets).
3. For r>n/2, there do not exist any disconnected r-regular graphs on n vertices.
The numbers of nonisomorphic not necessarily connected regular simple graphs with n nodes, illustrated above, are 1, 2, 2, 4, 3, 8, 6, 22, 26, 176, ... (OEIS A005176; Steinbach 1990).
See also
(0,2)-Graph, Cage Graph, Complete Graph, Completely Regular Graph, Configuration, Cubic Graph, Distance-Regular Graph, Irregular Graph, Moore Graph, Octic Graph, Quartic Graph, Quasi-Regular Graph, Quintic Graph, Septic Graph, Sextic Graph, Strongly Regular Graph, Superregular Graph, Two-Regular Graph, Vertex Degree, Weakly Regular GraphPortions of this entry contributed by Markus Meringer
Explore with Wolfram|Alpha
More things to try:
References
Bozóki S.; Szadoczki1, Z.; and Tekile, H. A. "Filling in Pattern Designs for Incomplete Pairwise Comparison Matrices: (Quasi-)Regular Graphs With Minimal Diameter." 13 May 2020. https://arxiv.org/abs/2006.01127.Chartrand, G. Introductory Graph Theory. New York: Dover, p. 29, 1985.Colbourn, C. J. and Dinitz, J. H. (Eds.). CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, p. 648, 1996.Comtet, L. "Asymptotic Study of the Number of Regular Graphs of Order Two on N." §7.3 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 273-279, 1974.Faradzev, I. A. "Constructive Enumeration of Combinatorial Objects." In Problèmes combinatoires et théorie des graphes (Orsay, 9-13 Juillet 1976). Colloq. Internat. du C.N.R.S. Paris: Centre Nat. Recherche Scient., pp. 131-135, 1978.Gropp, H. "Enumeration of Regular Graphs 100 Years Ago." Discrete Math. 101, 73-85, 1992.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 14 and 62, 1994.Meringer, M. "Connected Regular Graphs." http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html#CRG.Meringer, M. "Fast Generation of Regular Graphs and Construction of Cages." J. Graph Th. 30, 137-146, 1999.Petersen, J. "Die Theorie der regulären Graphs." Acta Math. 15, 193-220, 1891.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, 1998.Sachs, H. "On Regular Graphs with Given Girth." In Theory of Graphs and Its Applications: Proceedings of the Symposium, Smolenice, Czechoslovakia, 1963 (Ed. M. Fiedler). New York: Academic Press, 1964.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 159, 1990.Sloane, N. J. A. Sequences A005176/M0303, A005177/M0347, A006820/M1617, A006821/M3168, A006822/M3579, A014377, A014378, A014381, A014382, A014384, and A051031 in "The On-Line Encyclopedia of Integer Sequences."Steinbach, P. Field Guide to Simple Graphs. Albuquerque, NM: Design Lab, 1990.Wormald, N. "Generating Random Regular Graphs." J. Algorithms 5, 247-280, 1984.Zhang, C. X. and Yang, Y. S. "Enumeration of Regular Graphs." J. Dailan Univ. Tech. 29, 389-398, 1989.Referenced on Wolfram|Alpha
Regular GraphCite this as:
Meringer, Markus and Weisstein, Eric W. "Regular Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RegularGraph.html