RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2022 Volume 34, Issue 1, Pages 76–87 (Mi dm1698)

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


 English version:
Discrete Mathematics and Applications, 2023, 33:5, 273–281


© Steklov Math. Inst. of RAS, 2024