|
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$.
Received: 18.11.2020
Citation:
A. A. Makhnev, M. P. Golubyatnikov, “On small distance-regular graphs with the intersection arrays $\{mn-1,(m-1)(n+1)$, $n-m+1;1,1,(m-1)(n+1)\}$”, Diskr. Mat., 34:1 (2022), 76–87; Discrete Math. Appl., 33:5 (2023), 273–281
Linking options:
https://www.mathnet.ru/eng/dm1698https://doi.org/10.4213/dm1698 https://www.mathnet.ru/eng/dm/v34/i1/p76
|
Statistics & downloads: |
Abstract page: | 285 | Full-text PDF : | 69 | References: | 54 | First page: | 8 |
|