TOPICS
Search

Strongly Regular Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A k-regular simple graph G on nu nodes is strongly k-regular if there exist positive integers k, lambda, and mu such that every vertex has k neighbors (i.e., the graph is a regular graph), every adjacent pair of vertices has lambda common neighbors, and every nonadjacent pair has mu common neighbors (West 2000, pp. 464-465). A graph that is not strongly regular is said to be weakly regular.

A distance-regular graph with graph diameter d=2 is a strongly regular graph (Biggs 1993, p. 159). Strongly regular graphs are therefore distance-regular. Connected strongly regular graphs are conformally rigid (Steinerberger and Thomas 2024).

The complete graph K_n is strongly regular for all n>2. The status of the trivial singleton graph K_1 is unclear. Opinions differ on if K_2 is a strongly regular graph, though since it has no well-defined mu parameter, it is preferable to consider it not to be strongly regular (A. E. Brouwer, pers. comm., Feb. 6, 2013).

The graph complement of a non-empty non-complete strongly regular graph with parameters (nu,k,lambda,mu) is another strongly regular graph with parameters (nu,nu-k-1,nu-2-2k+mu,nu-2k+lambda).

A number of strongly regular graphs are implemented in the Wolfram Language as GraphData["StronglyRegular"].

StronglyRegularGraphs

The numbers of strongly regular graphs on nu=1, 2, ... nodes are 1, 1, 2, 4, 3, 6, 2, 6, 5, ... (OEIS A076435), the first few of which are illustrated above. The smallest regular graphs that are not strongly regular are the cycle graph C_6 and circulant graph Ci_6(2,3).

StronglyRegularGraphsConnected

Similarly, the numbers of connected strongly regular graphs on nu=1, 2, ... nodes are 1, 0, 1, 2, 2, 3, 1, 3, 3, ... (OEIS A088741).

Brouwer (2013) has conjectured that all connected strongly regular graphs (where K_2 is assumed to not be strongly regular) are Hamiltonian with the exception of the Petersen graph.

StronglyRegularTriangularGraphs

Other than the trivial singleton graph K_1 and the complete bipartite graphs K_(n,n), there are exactly seven known connected triangle-free strongly regular graphs, as summarized in the following table (Godsil 1995) and six of which are illustrated above. Determining the existence or absence of any others remains an open problem.

Vgraph
55-cycle graph
10Petersen graph
16Clebsch graph
50Hoffman-Singleton graph
56Gewirtz graph
77M22 graph
100Higman-Sims graph

Examples of connected non-complete strongly regular graphs are given in the following table.

(nu,k,lambda,mu)graph
(4,2,0,2)square graph
(5,2,0,1)cycle graph C_5
(6,3,0,3)utility graph
(6,4,2,4)octahedral graph
(8,4,0,4)complete bipartite graph K_(4,4)
(8,6,4,6)16-cell graph
(9,4,1,2)generalized quadrangle GQ(2,1)
(9,6,3,6)complete tripartite graph K_(3,3,3)
(10,3,0,1)Petersen graph
(10,5,0,5)complete bipartite graph K_(5,5)
(10,6,3,4)5-triangular graph
(10,8,6,8)5-cocktail party graph
(12,6,0,6)(6,6)-complete bipartite graph K_(6,6)
(12,8,4,8)(4,4,4)-complete tripartite graph K_(4,4,4)
(12,9,6,9)(3,3,3,3)-complete 4-partite graph K_(3,3,3,3)
(12,10,8,10)6-cocktail party graph
(13,6,2,3)13-Paley graph
(14,7,0,7)complete bipartite graph K_(7,7)
(14,12,10,12)7-cocktail party graph
(15,6,1,3)generalized quadrangle GQ(2,2)
(15,8,4,4)6-triangular graph
(15,10,5,10)complete tripartite graph K_(5,5,5)
(15,12,9,12)complete 5-partite graph K_(3,3,3,3,3)
(16,5,0,2)Clebsch graph
(16,6,2,2)(4,4)-rook graph, Shrikhande graph
(16,8,0,8)complete bipartite graph K_(8,8)
(16,9,4,6)complement of (4,4)-rook graph
(16,10,6,6)5-halved cube graph
(16,12,8,12)complete 4-partite graph K_(4,4,4,4)
(16,14,12,14)8-cocktail party graph
(17,8,3,4)17-Paley graph
(18,9,0,9)complete bipartite graph K_(9,9)
(18,12,6,12)complete tripartite graph K_(6,6,6)
(18,16,14,16)9-cocktail party graph
(20,10,0,10)complete bipartite graph K_(10,10)
(20,18,16,18)10-cocktail party graph
(21,10,3,6)(7,2)-Kneser graph
(21,10,5,4)7-triangular graph
(22,11,0,11)complete bipartite graph K_(11,11)
(22,20,18,20)11-cocktail party graph
(24,12,0,12)complete bipartite graph K_(12,12)
(24,22,20,22)12-cocktail party graph
(25,8,3,2)(5,5)-rook graph
(25,12,5,6)25-Paley graph, 25-Paulus graphs
(26,10,3,4)26-Paulus graphs
(26,13,0,13)complete bipartite graph K_(13,13)
(26,24,22,24)13-cocktail party graph
(27,10,1,5)generalized quadrangle GQ(2,4)
(27,16,10,8)Schläfli graph
(28,12,6,4)8-triangular graph, Chang graphs
(28,14,0,14)complete bipartite graph K_(14,14)
(28,15,6,10)(8,2)-Kneser graph
(28,26,24,26)14-cocktail party graph
(29,14,6,7)(29,14,6,7)-strongly regular graphs, 29-Paley graph
(30,15,0,15)complete bipartite graph K_(15,15)
(30,28,26,28)15-cocktail party graph
(32,16,0,16)complete bipartite graph K_(16,16)
(32,30,28,30)16-cocktail party graph
(34,17,0,17)complete bipartite graph K_(17,17)
(34,32,30,32)17-cocktail party graph
(36,10,4,2)(6,6)-rook graph
(36,14,4,6)U_3(3) graph
(36,14,7,4)9-triangular graph
(36,18,0,18)complete bipartite graph K_(18,18)
(36,21,10,15)(9,2)-Kneser graph
(36,34,32,34)18-cocktail party graph
(37,18,8,9)37-Paley graph
(38,19,0,19)complete bipartite graph K_(19,19)
(38,36,34,36)19-cocktail party graph
(40,20,0,20)complete bipartite graph K_(20,20)
(40,38,36,38)20-cocktail party graph
(41,20,9,10)41-Paley graph
(45,16,8,4)10-triangular graph
(45,28,15,21)(10,2)-Kneser graph
(49,12,5,2)(7,7)-rook graph
(49,24,11,12)49-Paley graph
(50,7,0,1)Hoffman-Singleton graph
(50,42,35,36)Hoffman-Singleton graph complement
(53,26,12,13)53-Paley graph
(55,18,9,4)11-triangular graph
(55,36,21,28)(11,2)-Kneser graph
(56,10,0,2)Gewirtz graph
(61,30,14,15)61-Paley graph
(63,32,16,16)(63,32,16,16)-strongly regular graph
(64,14,6,2)(8,8)-rook graph
(64,21,8,6)64-cyclotomic graph
(66,20,10,4)12-triangular graph
(66,45,28,36)(12,2)-Kneser graph
(73,36,17,18)73-Paley graph
(77,16,0,4)M22 graph
(78,22,11,4)13-triangular graph
(78,55,36,45)(13,2)-Kneser graph
(81,16,7,2)(9,9)-rook graph
(81,20,1,6)Brouwer-Haemers graph
(81,40,19,20)81-Paley graph
(89,44,21,22)89-Paley graph
(91,24,12,4)14-triangular graph
(91,66,45,55)(14,2)-Kneser graph
(97,48,23,24)97-Paley graph
(100,18,8,2)(10,10)-rook graph
(100,22,0,6)Higman-Sims graph
(100,36,14,12)Hall-Janko graph
(101,50,24,25)101-Paley graph
(105,26,13,4)15-triangular graph
(105,78,55,66)(15,2)-Kneser graph
(109,54,26,27)109-Paley graph
(112,30,2,10)generalized quadrangle GQ(3,9)
(113,56,27,28)113-Paley graph
(120,28,14,4)16-triangular graph
(120,56,28,24)(120,56,28,24)-strongly regular graph
(120,63,30,36)(120,63,30,36)-strongly regular graph
(121,60,29,30)121-Paley graph
(125,62,30,31)125-Paley graph
(136,30,15,4)17-triangular graph
(137,68,33,34)137-Paley graph
(149,74,36,37)149-Paley graph
(153,32,16,4)18-triangular graph
(157,78,38,39)157-Paley graph
(162,56,10,24)local McLaughlin graph
(169,84,41,42)169-Paley graph
(171,34,17,4)19-triangular graph
(190,36,18,4)20-triangular graph
(243,22,1,2)Berlekamp-van Lint-Seidel graph
(243,110,37,60)Delsarte graph
(253,112,36,60)(253,112,36,60)-strongly regular graph
(275,112,30,56)McLaughlin graph
(416,100,36,20)G_2(4) graph
(729,112,1,20)Games graph

Strongly regular graphs with lambda=mu correspond to symmetric balanced incomplete block designs (West 2000, p. 465).

See also

Clebsch Graph, Conference Graph, Directed Strongly Regular Graph, Gewirtz Graph, Higman-Sims Graph, Hoffman-Singleton Graph, Regular Graph, Weakly Regular Graph

Explore with Wolfram|Alpha

References

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.Brouwer, A. E. and van Lint, J. H. "Strongly Regular Graphs and Partial Geometries." In Enumeration and Design: Papers from the Conference on Combinatorics Held at the University of Waterloo, Waterloo, Ont., June 14-July 2, 1982 (Ed. D. M. Jackson and S. A. Vanstone). Toronto, Canada: Academic Press, pp. 85-122, 1984.Brouwer, A. E. and van Maldeghem, H. Strongly Regular Graphs. Cambridge, England: Cambridge University Press, 2022.Cohen, N. and Pasechnik,  D. V. "Implementing Brouwer's Database of Strongly Regular Graphs." 20 Jul 2016. https://arxiv.org/abs/1601.00181.DistanceRegular.org. "SRG(29,14,6,7) (40 graphs, 20 pairs)." http://www.distanceregular.org/graphs/srg29.14.6.7.html.DistanceRegular.org. "SRG(176,70,18,34)." http://www.distanceregular.org/graphs/srg176.70.18.34.html.DistanceRegular.org. "SRG(176,105,68,54)." http://www.distanceregular.org/graphs/srg176.105.68.54.html.Godsil, C. D. "Triangle-Free Strongly Regular Graphs." Problem 2 in "Problems in Algebraic Combinatorics." Elec. J. Combin. 2, No. F1, pp. 1-20, 1995. http://www.combinatorics.org/Volume_2/Abstracts/v2i1f1.html.McKay, B. "Strongly Regular Graphs." http://cs.anu.edu.au/~bdm/data/graphs.html.Royle, G. "Strongly Regular Graphs." http://school.maths.uwa.edu.au/~gordon/remote/srgs/.Seidel, J. J. "Strongly Regular Graphs." In Surveys in Combinatorics (Proc. Seventh British Combinatorial Conf., Cambridge, 1979). Cambridge, England: Cambridge University Press, pp. 157-180, 1979.Sloane, N. J. A. Sequences A076435 and A088741 in "The On-Line Encyclopedia of Integer Sequences."Spence, E. "Strongly Regular Graphs on at Most 64 Vertices." http://www.maths.gla.ac.uk/~es/srgraphs.html.Steinerberger, S. and Thomas, R. R. "Conformally Rigid Graphs." 19 Feb 2024. https://arxiv.org/abs/2402.11758.Thas, J. A. "Combinatorics of Partial Geometries and Generalized Quadrangles." In Higher Combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976). Dordrecht, Netherlands: Reidel, pp. 183-199, 1977.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

Referenced on Wolfram|Alpha

Strongly Regular Graph

Cite this as:

Weisstein, Eric W. "Strongly Regular Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/StronglyRegularGraph.html

Subject classifications