Strongly regular graphs $(v,k,0,2)$ of degree $k>10$: do they exist? (Kourovka 8.77)
Statement
A *strongly regular graph* with parameters $(v,k,0,2)$ is a $k$-regular graph on $v$ vertices in which any two adjacent vertices have no common neighbour ($\lambda=0$) and any two non-adjacent vertices have exactly two common neighbours ($\mu=2$); such a graph necessarily has girth 4. Do there exist strongly regular graphs with parameters $(v,k,0,2)$ of degree $k>10$? Nontrivial (primitive) examples are known only for $k=5$ — the Clebsch graph, $(16,5,0,2)$ — and $k=10$ — the Gewirtz graph, $(56,10,0,2)$; together with the small degenerate cases $k\le 2$ (e.g. the 4-cycle, $(4,2,0,2)$) this exhausts the known degrees, $k\in\{1,2,5,10\}$. The automorphism group of such a graph is a rank-3 primitive permutation group, which is why the problem sits in the Kourovka Notebook.
Acceptance. FULLY RESOLVES: EITHER an explicit adjacency matrix of a strongly regular graph (v,k,0,2) with k>10, together with a verification script confirming k-regularity, lambda=0 and mu=2 — a finite, machine-checkable certificate settling existence affirmatively — OR a rigorous nonexistence proof for the smallest open feasible case (352,26,0,2) (a major advance), and more broadly across the infinite feasible family k in {26,37,50,82,...} (which would fully settle the problem). ADVANCES: a machine-checkable nonexistence proof for a single feasible parameter set with k>10 — e.g. exhausting the rank-3 automorphism-group candidates for (352,26,0,2) supplied by CFSG and eliminating each — or a verified exhaustive search under a prescribed automorphism group. Numerical or heuristic near-constructions without an exact certificate do NOT qualify.
Background
Source: The Kourovka Notebook, No. 21, arXiv:1401.0300 (v44, June 2026), Problem 8.77, posed by D. G. Fon-Der-Flaass (8th Issue, 1982): 'Do there exist strongly regular graphs with parameters lambda = 0, mu = 2 of degree k > 10? Such graphs are known for k = 5 and k = 10, their automorphism groups are primitive permutation groups of rank 3.' Feasibility: integrality of the eigenvalue multiplicities forces k = t^2+1 with multiplicity m = [k+(v-1)(t-1)]/(2t) an integer; this yields k=5 (Clebsch) and k=10 (Gewirtz), rules out k=17, and makes (352,26,0,2) the smallest open feasible case, followed by (704,37,0,2), then k=50, k=82, and so on. Crucially, N. L. Biggs proved that for mu not in {2,4,6} only finitely many (0,mu)-graphs exist; mu=2 is one of the three exceptional values, so the degree k is NOT bounded a priori — the problem is genuinely open, not almost-finite. The existing literature on the family is entirely conditional automorphism analysis, not existence: A. A. Makhnev, 'On automorphisms of strongly regular graphs with lambda=0, mu=2', Sb. Math. 195 (2004); Nakagawa's automorphism bounds; Makhnev-school papers on a hypothetical (352,26,0,2) graph. Brouwer's SRG tables list these parameter sets as open. Vetted open as of 2026-07-06: neither a construction with k>10 nor any nonexistence theorem appeared in 2020–2026. Nuance: this is combinatorics housed in Kourovka (a (v,k,0,2)-SRG forces a rank-3 group), and the SRG community (Makhnev, Brouwer) actively touches the family, so neglect is only moderate — but the existence question is unambiguously open.
References
Investigations · 0
No published investigations yet. This problem is unclaimed territory.