TOPICS

# Strongly Regular Graph

A -regular simple graph on nodes is strongly -regular if there exist positive integers , , and such that every vertex has neighbors (i.e., the graph is a regular graph), every adjacent pair of vertices has common neighbors, and every nonadjacent pair has 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 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 is strongly regular for all . The status of the trivial singleton graph is unclear. Opinions differ on if is a strongly regular graph, though since it has no well-defined 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 is another strongly regular graph with parameters .

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

The numbers of strongly regular graphs on , 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 and circulant graph .

Similarly, the numbers of connected strongly regular graphs on , 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 is assumed to not be strongly regular) are Hamiltonian with the exception of the Petersen graph.

Other than the trivial singleton graph and the complete bipartite graphs , 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.

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

 graph square graph cycle graph utility graph octahedral graph complete bipartite graph 16-cell graph generalized quadrangle GQ(2,1) complete tripartite graph Petersen graph complete bipartite graph 5-triangular graph 5-cocktail party graph (6,6)-complete bipartite graph (4,4,4)-complete tripartite graph (3,3,3,3)-complete 4-partite graph 6-cocktail party graph 13-Paley graph complete bipartite graph 7-cocktail party graph generalized quadrangle GQ(2,2) 6-triangular graph complete tripartite graph complete 5-partite graph Clebsch graph (4,4)-rook graph, Shrikhande graph complete bipartite graph complement of (4,4)-rook graph 5-halved cube graph complete 4-partite graph 8-cocktail party graph 17-Paley graph complete bipartite graph complete tripartite graph 9-cocktail party graph complete bipartite graph 10-cocktail party graph (7,2)-Kneser graph 7-triangular graph complete bipartite graph 11-cocktail party graph complete bipartite graph 12-cocktail party graph (5,5)-rook graph 25-Paley graph, 25-Paulus graphs 26-Paulus graphs complete bipartite graph 13-cocktail party graph generalized quadrangle GQ(2,4) Schläfli graph 8-triangular graph, Chang graphs complete bipartite graph (8,2)-Kneser graph 14-cocktail party graph (29,14,6,7)-strongly regular graphs, 29-Paley graph complete bipartite graph 15-cocktail party graph complete bipartite graph 16-cocktail party graph complete bipartite graph 17-cocktail party graph (6,6)-rook graph graph 9-triangular graph complete bipartite graph (9,2)-Kneser graph 18-cocktail party graph 37-Paley graph complete bipartite graph 19-cocktail party graph complete bipartite graph 20-cocktail party graph 41-Paley graph 10-triangular graph (10,2)-Kneser graph (7,7)-rook graph 49-Paley graph Hoffman-Singleton graph Hoffman-Singleton graph complement 53-Paley graph 11-triangular graph (11,2)-Kneser graph Gewirtz graph 61-Paley graph (63,32,16,16)-strongly regular graph (8,8)-rook graph 64-cyclotomic graph 12-triangular graph (12,2)-Kneser graph 73-Paley graph M22 graph 13-triangular graph (13,2)-Kneser graph (9,9)-rook graph Brouwer-Haemers graph 81-Paley graph 89-Paley graph 14-triangular graph (14,2)-Kneser graph 97-Paley graph (10,10)-rook graph Higman-Sims graph Hall-Janko graph 101-Paley graph 15-triangular graph (15,2)-Kneser graph 109-Paley graph generalized quadrangle GQ(3,9) 113-Paley graph 16-triangular graph (120,56,28,24)-strongly regular graph (120,63,30,36)-strongly regular graph 121-Paley graph 125-Paley graph 17-triangular graph 137-Paley graph 149-Paley graph 18-triangular graph 157-Paley graph local McLaughlin graph 169-Paley graph 19-triangular graph 20-triangular graph Berlekamp-van Lint-Seidel graph Delsarte graph (253,112,36,60)-strongly regular graph McLaughlin graph graph Games graph

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

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

More things to try:

## 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. " (40 graphs, 20 pairs)." http://www.distanceregular.org/graphs/srg29.14.6.7.html.DistanceRegular.org. "." http://www.distanceregular.org/graphs/srg176.70.18.34.html.DistanceRegular.org. "." 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