Kourovka Notebook Problem 8.77

Definitions and mathematical statement

Use the conventional interpretation of a strongly regular graph as a finite simple undirected graph that is neither complete nor edgeless; the supplied statement does not explicitly specify these conventions. For such a graph $\Gamma=(V,E)$, write $v=|V|$ and $N(x)=\{y\in V:\{x,y\}\in E\}$. The graph has parameters $(v,k,\lambda,\mu)$ if every vertex has exactly $k$ neighbors, every pair of adjacent vertices has exactly $\lambda$ common neighbors, and every pair of distinct nonadjacent vertices has exactly $\mu$ common neighbors.

Problem (D. G. Fon-Der-Flaass, 1982). Do there exist integers $v,k$ with $10<k<v-1$ and a finite simple undirected graph $\Gamma=(V,E)$, with $|V|=v$, such that \[ \begin{aligned} |N(x)|&=k &&\text{for every }x\in V,\\ |N(x)\cap N(y)|&=0 &&\text{for every }\{x,y\}\in E,\\ |N(x)\cap N(y)|&=2 &&\text{for all distinct }x,y\in V\text{ with }\{x,y\}\notin E? \end{aligned} \] The supplied source states that examples with $k=5$ and $k=10$ are known and that their automorphism groups act primitively with permutation rank $3$. Here an automorphism is a permutation of $V$ preserving adjacency; a permutation group is primitive if it is transitive and preserves no partition other than the singleton partition and the one-part partition. Permutation rank $3$ means that the induced action on $V\times V$ has exactly three orbits, here the diagonal, the ordered adjacent pairs, and the ordered distinct nonadjacent pairs. These automorphism properties describe the cited known examples and are not additional requirements on the graphs sought.

Short English statement

Does there exist a finite strongly regular graph of degree greater than $10$ in which adjacent vertices have no common neighbors and distinct nonadjacent vertices have exactly two common neighbors? The supplied source reports examples of degrees $5$ and $10$, with primitive rank-$3$ automorphism groups. The registry labels the problem open; that label is supplied curation, not an independently verified assessment.

Sources

• Supplied local UnsolvedMath registry record: permanent ID $700525$, exact source code catalogue entry, title Kourovka Notebook Problem 8.77. The record supplies the status open.
• The Kourovka Notebook (Unsolved Problems in Group Theory), original problem $8.77$, 8th issue (1982), proposed by D. G. Fon-Der-Flaass. The supplied background identifies the 21st issue edition (2026), arXiv:1401.0300v48; the collection description names E. I. Khukhro and V. D. Mazurov as editors.