Regular Graph (original) (raw)
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology
Alphabetical Index New in MathWorld
A simple graph is said to be regular of degree 
if all vertex degrees are the same number 
. 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 
-arc-transitive graphs are sometimes also called "
-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 
except for a single vertex whose degree is 
may be called a quasi-regular graph (Bozóki et al. 2020).
A semirandom 
-regular graph can be generated using RegularGraph[k,_n_] in the Wolfram Language package Combinatorica` .
The following table lists the names of low-order 
-regular graphs.
Some regular simple graphs of degree higher than 5 are summarized in the following table.
-regular graphs
,
graph
graph, 
graph, 
graph
The numbers of nonisomorphic connected regular graphs of order 
, 2, ... are 1, 1, 1, 2, 2, 5, 4, 17, 22, 167, ... (OEIS A005177; Steinbach 1990).
For an 
-regularsimple graph on 
nodes,
where 
is the edge count. Let 
be the number of connected 
-regular graphs with 
points. Then 
, 
, and 
when both 
and 
are odd. Zhang and Yang (1989) give 
for 
, and Meringer provides a similar tabulation including complete enumerations for low orders.
The following table gives the numbers 
of connected 
-regular simple graphs for small numbers of nodes 
(Meringer 1999, Meringer).
Typically, only numbers of connected 
-regular graphs on 
vertices are published for 
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 
-regular graphs on 
vertices can be obtained from numbers of connected 
-regular graphs on 
vertices.
2. Numbers of not-necessarily-connected 
-regular graphs on 
vertices equal the number of not-necessarily-connected 
-regular graphs on 
vertices (since building complementary graphs defines a bijection between the two sets).
3. For 
, there do not exist any disconnected 
-regular graphs on 
vertices.
The numbers of nonisomorphic not necessarily connected regular simple graphs with 
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 Graph
Portions of this entry contributed by Markus Meringer
Explore with Wolfram|Alpha
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 
." §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. SequencesA005176/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
Cite this as:
Meringer, Markus and Weisstein, Eric W. "Regular Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RegularGraph.html