# Open cases in the table of strongly regular graphs

A strongly regular graph is a regular graph in which the number of common neighbours of two vertices depends only on whether they are adjacent. Many parameter sets pass every known feasibility test, yet nobody knows whether a graph exists. Andries Brouwer's table records the status of each set; the smallest open one has 88 vertices, and a candidate graph is verified in milliseconds.

## Problem

A graph on $v$ vertices is *strongly regular* with parameters $(v, k, \lambda, \mu)$ if it is $k$-regular, every two adjacent vertices have exactly $\lambda$ common neighbours, and every two non-adjacent vertices have exactly $\mu$ common neighbours. In terms of its adjacency matrix $A$,

$$A^2 = k I + \lambda A + \mu (J - I - A),$$

where $J$ is the all-ones matrix. Arithmetic conditions (integral eigenvalue multiplicities, the Krein conditions, the absolute bound and others) rule out many parameter sets.

**Task:** decide existence for the parameter sets that Brouwer's table lists as open, other than Conway's $(99, 14, 1, 2)$, which has a project of its own (conway-99-graph). The smallest are $(88, 27, 6, 9)$, $(100, 33, 8, 12)$, $(111, 30, 5, 9)$, $(115, 18, 1, 3)$, $(121, 36, 7, 12)$ and $(121, 48, 17, 20)$.

## Background

Strongly regular graphs sit between combinatorics, finite geometry, coding theory and group theory: they arise from generalized quadrangles, partial geometries, projective two-weight codes, orthogonal arrays and classical groups. Brouwer's table lists parameter sets up to 1300 vertices, marked as existing, not existing (with the reason, such as the absolute bound or the Krein conditions) or unknown, with constructions and nonexistence proofs cited for each. Settling a case has required anything from clever algebraic constructions to exhaustive computer searches.

## What is known

- **Recently settled:** $(65, 32, 15, 16)$ exists (Gritsenko, 2021, from an adjacency matrix built of circulant blocks); $(85, 14, 3, 2)$ does not (Shpectorov and Zhao, 2025, by exhaustive enumeration of local structures); $(75, 32, 10, 16)$ and $(95, 40, 12, 20)$ do not (Azarija and Marc, 2015–2016); $(76, 30, 8, 14)$ does not (Bondarenko, Prymak and Radchenko, 2014).
- **October 2026, not yet refereed:** a series of Zenodo preprints by Anton Kovaľ, which the table records as "Kovaľ + AI", rules out further sets such as $(69, 20, 7, 5)$, $(96, 35, 10, 14)$ and $(99, 42, 21, 15)$, and gives constructions and uniqueness results for others.
- **Smallest open sets** (as of October 2026): $(88, 27, 6, 9)$ with eigenvalues $3$ and $-6$; Conway's $(99, 14, 1, 2)$; $(100, 33, 8, 12)$; then the sets listed in the task, and more above 130 vertices.

## What would count as progress

- A graph for an open parameter set, given by its adjacency matrix or edge list. Checking the matrix identity above takes milliseconds.
- A nonexistence proof, either by an argument that can be checked by hand or by an exhaustive search whose code and certificates can be rerun.
- Independent verification of the recent preprints, which the table already relies on.

## References

1. O. Gritsenko, "On strongly regular graph with parameters (65; 32; 15; 16)" (2021). [arXiv:2102.05432](https://arxiv.org/abs/2102.05432)
2. S. Shpectorov and T. Zhao, "Strongly regular graphs with parameters (85,14,3,2) do not exist", *Journal of Combinatorial Theory, Series A* 225 (2027), 106242. [arXiv:2504.02449](https://arxiv.org/abs/2504.02449)
3. J. Azarija and T. Marc, "There is no (75,32,10,16) strongly regular graph" (2015). [arXiv:1509.05933](https://arxiv.org/abs/1509.05933)
4. A. V. Bondarenko, A. Prymak and D. Radchenko, "Non-existence of (76,30,8,14) strongly regular graph and some structural tools" (2014). [arXiv:1410.6748](https://arxiv.org/abs/1410.6748)

## Source

Imported from [Parameters of strongly regular graphs (A. E. Brouwer), 51–100 vertices](https://aeb.win.tue.nl/graphs/srg/srgtab51-100.html), curated by Andries E. Brouwer. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.