Kourovka Notebook Problem 20.53

Definitions and mathematical statement

Let $q\geq 3$ be an integer. A prime power means an integer $p^e$, where $p$ is prime and $e\geq 1$ is an integer. Let $H=(V,E)$ be a connected simple undirected graph of diameter $3$, and let $d$ denote graph distance. For $y\in V$, write $H(y)=\{z\in V:\{y,z\}\in E\}$. The graph is distance-regular with intersection array \[ \{b_0,b_1,b_2;c_1,c_2,c_3\} \] if, for every ordered pair $(x,y)$ with $d(x,y)=i$, the quantities \[ \left|\{z\in H(y):d(x,z)=i+1\}\right|=b_i\quad(0\leq i\leq 2) \] and \[ \left|\{z\in H(y):d(x,z)=i-1\}\right|=c_i\quad(1\leq i\leq 3) \] depend only on $i$. Such a graph is finite because it has finite valency and finite diameter.

Existence question. Does there exist an integer $q\geq 3$ which is not a prime power and a distance-regular graph $H$ with intersection array \[ \{q(q-1),(q+1)(q-2),q+1;1,1,q(q-2)\}? \] The integer domain and the restriction $q\geq 3$ follow from the standard diameter-three interpretation: $b_2=q+1$ is an integer, and $b_1,b_2,c_3$ must be positive. In particular, $q=2$ does not give an intersection array of a diameter-three graph.

Supplied context and qualifications. The source describes a nonisotropic unitary graph $\Gamma$, for prime-power $q$, with this intersection array, and states that $G=\operatorname{Aut}(\Gamma)$ acts transitively on its vertices and on its unordered edges. It also states that $\Gamma$ is distance-transitive for $q=3$, meaning that its automorphism group is transitive on ordered vertex pairs at each fixed distance. These are supplied background assertions, not independently verified here. The source does not define the nonisotropic unitary construction or specify its parameter exceptions; its prime-power assertion therefore requires qualification at $q=2$ under the diameter-three convention. The final existence question asks only for distance-regularity with the displayed array; it does not explicitly require the sought graph to be unitary, vertex-transitive, edge-transitive, or distance-transitive.

Short English statement

Does some integer $q\geq 3$ that is not a prime power admit a distance-regular graph of diameter $3$ with the displayed intersection array? The supplied prime-power unitary examples provide context; the final question imposes no explicit automorphism-transitivity requirement. The registry labels the problem open, without independent verification here.

Sources

• Local UnsolvedMath registry, permanent ID $701711$, exact source problem code catalogue entry, title Kourovka Notebook Problem 20.53; supplied upstream revision d371ee917ac9647fbb06cd6fc529deec6f3dda82. The supplied record is labelled open; this is a source label, not an independently verified literature assessment.
• A. A. Makhnev, Problem 20.53, proposed in 2022, in The Kourovka Notebook (Unsolved Problems in Group Theory). The supplied background identifies the 20th issue (2022) and the 21st issue edition (2026), with identifier arXiv:1401.0300v48. The supplied collection description names E. I. Khukhro and V. D. Mazurov as editors. This attribution and edition information are supplied evidence; the referenced source has not been independently consulted here.