TOPICS
Search

Regular Graph


A graph is said to be regular of degree r if all local 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 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 graphs of degree higher than 5 are summarized in the following table.

rr-regular graphs
6Menger dual of the Gray configuration, halved Foster graph, Hoffman-Singleton Graph minus star, Kummer graph, Perkel graph, Reye graph, Shrikhande graph, 16-cell graph
7doubly truncated Witt graph, bipartite double of the Hoffman-Singleton graph, Hoffman-Singleton graph, Klein graph
824-cell graph, line graph of the icosahedral graph
10Conway-Smith graph, bipartite double of the Gewirtz graph, Gewirtz graph, Hall-Janko near octagon
12line graph of the Hoffman-Singleton graph, Kronecker product of the icosahedral graph complement and the ones matrix J_2, 600-cell graph
14distance-2 graph of the Klein graph, U_3(3) graph
15truncated Witt graph
16bipartite double of the M_(22) graph, M_(22) graph, Schläfli graph
20Brouwer-Haemers graph, Kronecker product of the Petersen line graph complement and the ones matrix J_2
22bipartite double of the Higman-Sims graph, Higman-Sims graph
27Gosset graph
30large Witt graph
36Hall-Janko graph
42Hoffman-Singleton graph complement
56local McLaughlin graph
100G_2(4) graph
112McLaughlin graph
416Suzuki graph
RegularConnectedGraphs

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 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 graphs for small numbers of nodes n (Meringer 1999, Meringer).

SloaneA002851A006820A006821A006822A014377A014378A014381A014382A014384
classcubicquarticquinticsexticsepticoctic
nN(n,3)N(n,4)N(n,5)N(n,6)N(n,7)N(n,8)N(n,9)N(n,10)N(n,11)N(n,12)
41000000000
50100000000
62110000000
70201000000
85631100000
901604010000
1019596021511000
1102650266060100
12851544784878491547949110
13010778036786001078601001
145098816834593832160930021609301345938688193540131
15080549101470293675014702936760805579017
16406080374182585136675258513674180377964207
17086221634000086223660
1841301985870522
1900000
20510489
2100000
227319447
2300000
24117940535
2500000
262094480864
nN(n,13)N(n,14)N(n,15)N(n,16)N(n,17)N(n,18)N(n,19)N(n,20)N(n,21)N(n,22)
130000000000
141000000000
150100000000
1621110000000
1702501000000
1898588387342110331100000
190039010000
205163444911000
21000600100
22737392473110
2300008801
241185735921101
2500000130
262103205738

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.

RegularGraphs

The numbers of nonisomorphic not necessarily connected regular 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, Local Degree, Moore Graph, Octic Graph, Quartic Graph, Quasi-Regular Graph, Quintic Graph, Septic Graph, Sextic Graph, Strongly Regular Graph, Superregular Graph, Two-Regular Graph, 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 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 Graph

Cite this as:

Meringer, Markus and Weisstein, Eric W. "Regular Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RegularGraph.html

Subject classifications