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

Diskretnaya Matematika, Tome 34 (2022) no. 1, pp. 76-87

Résumé

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.

Détail

Keywords: distance-regular graph, graph $\Gamma$ with a strongly regular graph $\Gamma_3$.