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 graph9-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 complement53-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 graphGames
graph
Strongly regular graphs with 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.
"
(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
Subject classifications More... Less...