A strongly regular graph, in the convention used here, is a 
-regular simple graph 
other than 
on 
vertices for which
there exist nonnegative 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 regular graph that is not strongly regular is
said to be weakly regular.
The parameter 
here is unrelated to the 
used for the mutual-visibility
number, the 
of the matching polynomial, and the 
used for circuit rank.
A distance-regular graph with graph diameter 
is a strongly regular graph (Biggs 1993, p. 159). Strongly regular graphs are
distance-regular, including disconnected
graphs under the convention used here. A connected
strongly regular graph that is not a complete graph
has graph diameter 2. Connected strongly regular
graphs on at least three vertices are conformally
rigid (Steinerberger and Thomas 2025).
This convention includes the singleton graph 
, empty
graphs of positive order, and the complete graph 
for all 
. The common-neighbor condition for nonadjacent pairs
is vacuous in a complete graph, as is that for
adjacent pairs in an empty graph. Opinions differ
on whether to include 
as a strongly regular graph. It is excluded here (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
.
The adjacency matrix 
of a non-empty non-complete strongly regular graph satisfies
 |
(1)
|
where 
is the identity matrix and 
is the matrix whose entries are all 1 (Brouwer and Haemers
2012). The diagonal entries of 
give the vertex degrees,
and each off-diagonal entry counts the common neighbors
of the corresponding vertices. Consequently, checking
this identity verifies all the common-neighbor conditions.
On eigenvectors perpendicular to the vector whose entries are all 1, 
acts as zero. The corresponding graph
eigenvalues therefore satisfy
 |
(2)
|
In particular, the least graph eigenvalue is
 |
(3)
|
and the Hoffman ratio bound gives
![chi(G)>=[1-k/s],](/images/equations/StronglyRegularGraph/NumberedEquation4.svg) |
(4)
|
where 
is the chromatic number and ![[x]](/images/equations/StronglyRegularGraph/Inline28.svg)
is the ceiling function.
This also applies to disconnected strongly
regular graphs, which are disjoint unions of equally sized complete
graphs and have 
. Complete graphs and
empty graphs have chromatic
number 
and 1, respectively.
A number of strongly regular graphs are implemented in the Wolfram Language as GraphData["StronglyRegular"].
The 
strongly regular graph and its graph complement,
the 
strongly regular graph, both have the Mathieu group
M22, of order 
, as their automorphism
group (DistanceRegular.org). The 
strongly regular graph has the Mathieu
group M23, of order 
, as its automorphism
group (DistanceRegular.org).
The numbers of strongly regular graphs on 
, 2, ... nodes are 1, 1, 2, 4, 3, 6, 2, 6, 5, ... (OEIS
A076435, with 
excluded), the first few of which are illustrated above.
Apart from 
,
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, with 
excluded).
Brouwer and Haemers (2008) 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, pp. 3-4)
and six of which are illustrated above. Determining the existence or absence of any
others remains an open problem.
 | graph |
| 5 | 5-cycle graph |
| 10 | Petersen graph  |
| 16 | Clebsch graph |
| 50 | Hoffman-Singleton graph |
| 56 | Gewirtz graph |
| 77 | M22 graph |
| 100 | Higman-Sims graph |
Examples of connected non-complete strongly regular graphs are given in the following table.
graph
graph
For a nonempty strongly regular graph with 
, the open
graph neighborhoods form a symmetric block
design (West 2000, p. 465). Strongly regular graphs also arise as point
graphs of partial geometries. In this context,
a graph with the corresponding parameter set is a pseudogeometric
graph; when the incidence structure exists
and its lines give the Delsarte
cliques, the graph is a geometric graph. For
example, the McLaughlin graph has the parameters
of a point graph of a partial
geometry 
,
but the corresponding McLaughlin geometry
does not exist (Östergård and Soicher 2018).
Graph." 
(40 graphs, 20 pairs)." 
."
."