On small distance-regular graphs with the intersection arrays $\{mn-1,(m-1)(n+1)$, $n-m+1;1,1,(m-1)(n+1)\}$
A. A. Makhnev,
M. P. Golubyatnikov N.N. Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg
Abstract:
Let
$\Gamma$ be a diameter 3 distance-regular graph with a strongly regular graph
$\Gamma_3$, where
$\Gamma_3$ is the graph whose vertex set coincides with the vertex set of the graph
$\Gamma$ and two vertices are adjacent whenever they are at distance
$3$ in the graph
$\Gamma$. Computing the parameters of
$\Gamma_3$ by the intersection array of the graph
$\Gamma$ is considered as the direct problem. Recovering the intersection array of the graph
$\Gamma$ by the parameters of
$\Gamma_3$ is referred to as the inverse problem. The inverse problem for
$\Gamma_3$ has been solved earlier by A. A. Makhnev and M. S. Nirova. In the case where
$\Gamma_3$ is a pseudo-geometric graph of a net, a series of admissible intersection arrays has been obtained: $\{c_2(u^2-m^2)+2c_2m-c_2-1,c_2(u^2-m^2),(c_2-1)(u^2-m^2)+2c_2m-c_2;1,c_2,{u^2-m^2}\}$ (A. A. Makhnev, Wenbin Guo, M. P. Golubyatnikov). The cases
$c_2=1$ and
$c_2=2$ have been examined by A. A. Makhnev, M. P. Golubyatnikov and A. A. Makhnev, M. S. Nirova, respectively. In this paper in the class of graphs with the intersection arrays
$\{mn-1,{(m-1)(n+1)}$,
${n-m+1};1,1,(m-1)(n+1)\}$ all admissible intersection arrays for
${3\le m\le 13}$ are found:
$\{20,16,5;1,1,16\}$,
$\{39,36,4;1,1,36\}$,
$\{55,54,2;1,2,54\}$,
$\{90,84,7;1,1,84\}$,
$\{220,216,5;1,1,216\}$,
$\{272,264,9;1,1,264\}$ and
$\{350,336,15;1,1,336\}$. It is demonstrated that graphs with the intersection arrays
$\{20,16,5;1,1,16\}$,
$\{39,36,4;1,1,36\}$ and
$\{90,84,7;1,1,84\}$ do not exist.
Keywords:
distance-regular graph, graph $\Gamma$ with a strongly regular graph $\Gamma_3$.
UDC:
519.172 Received: 18.11.2020
DOI:
10.4213/dm1698