Small distance-regular graphs with intersection arrays $\{mn-1,(m-1)(n+1),n-m+1;1,1,(m-1)(n+1)\}$

Let $\Gamma$ be a distance-regular graph of diameter 3 with strongly regular graph $\Gamma_3$, where $\Gamma_3$ have the same vertices as $\Gamma$, and two vertices are adjacent in $\Gamma_3$ if and only if the distance between them in $\Gamma$ is equal to $3$ (see [1]).

Problem. Find an intersection array of a distance-regular graph $\Gamma$ if $\Gamma_3$ is strongly regular and the parameters of $\Gamma_3$ are known.

If $\Gamma_3$ is a pseudo-geometric graph of a net, then there is the following infinite series of feasible intersection arrays $\{mn-1,(m-1)(n+1),n-m+1;1,1,(m-1)(n+1)\}$ (see [2]). We consider intersection arrays from this series for some small parameters $n$ and $m$ and prove the following theorem.

Theorem Distance-regular graphs with intersection arrays $\{20,16,5;1,1,16\}$ and $\{39,36,4;1,1,36\}$ do not exist.

Our poof of Theorem is based on calculations of triple intersection numbers (see [3]).

Acknowledgement. This work was supported by the Russian Science Foundation (project 19-71-10067).


Список литературы

1. A. E. Brouwer, A. M. Cohen, A. Neumaier, Distance-Regular Graphs, Springer-Verlag, 1989
2. A. Makhnev, M. Golubyatnikov, W. Guo, “Inverse Problems in Graph Theory: Nets”, Communications in Mathematics and Statistics, 7:1 (2019), 69–8
3. K. Coolsaet, A. Jurišić, “Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs”, J. Comb. Theory, Series A., 115 (2008), 1086–1095