Geodesic
On small distance-regular graphs with the intersection arrays $\{mn-1,(m-1)(n+1)$, $n-m+1;1,1,(m-1)(n+1)\}$
Diskretnaya Matematika, Tome 34 (2022) no. 1, pp. 76-87.

Voir la notice de l'article provenant de la source Math-Net.Ru

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$. 
@article{DM_2022_34_1_a5,
     author = {A. A. Makhnev and M. P. Golubyatnikov},
     title = {On small distance-regular graphs with the intersection arrays $\{mn-1,(m-1)(n+1)$, $n-m+1;1,1,(m-1)(n+1)\}$},
     journal = {Diskretnaya Matematika},
     pages = {76--87},
     publisher = {mathdoc},
     volume = {34},
     number = {1},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2022_34_1_a5/}
}
TY  - JOUR
AU  - A. A. Makhnev
AU  - M. P. Golubyatnikov
TI  - On small distance-regular graphs with the intersection arrays $\{mn-1,(m-1)(n+1)$, $n-m+1;1,1,(m-1)(n+1)\}$
JO  - Diskretnaya Matematika
PY  - 2022
SP  - 76
EP  - 87
VL  - 34
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2022_34_1_a5/
LA  - ru
ID  - DM_2022_34_1_a5
ER  - 
%0 Journal Article
%A A. A. Makhnev
%A M. P. Golubyatnikov
%T On small distance-regular graphs with the intersection arrays $\{mn-1,(m-1)(n+1)$, $n-m+1;1,1,(m-1)(n+1)\}$
%J Diskretnaya Matematika
%D 2022
%P 76-87
%V 34
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2022_34_1_a5/
%G ru
%F DM_2022_34_1_a5
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)\}$. Diskretnaya Matematika, Tome 34 (2022) no. 1, pp. 76-87. http://geodesic.mathdoc.fr/item/DM_2022_34_1_a5/

[1] A.E. Brouwer, A.M. Cohen, A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin Heidelberg New York, 1989 | MR | Zbl

[2] A. A. Makhnev, M. S. Nirova, “Distantsionno regulyarnye grafy Shilla s $b_2=c_2$”, Matem. zametki, 103:5 (2018), 730–744 | MR | Zbl

[3] A. Makhnev, M. Golubyatnikov, Wenbin Guo, “Inverse problems in graph theory: nets”, Comm. Math. Stat., 7:1 (2019), 69–83 | DOI | MR | Zbl

[4] A. A. Makhnev, M. P. Golubyatnikov, “Avtomorfizmy grafa s massivom peresechenii $\{nm-1,nm-n+m-1,n-m+1;1,1,nm-n+m-1\}$”, Algebra i logika, 59:5 (2020), 567–581 | MR | Zbl

[5] A. A. Makhnev, M. S. Nirova, “O distantsionno regulyarnykh grafakh s $c_2=2$”, Diskretnaya matematika, 32:1 (2020), 74–80

[6] A. A. Makhnev, “Avtomorfizmy distantsionno regulyarnogo grafa s massivom peresechenii $\{24,18,9;1,1,16\}$”, Sib. elektron. matem. izv., 16 (2019), 1547–1552 | MR | Zbl

[7] M. P. Golubyatnikov, “Ob avtomorfizmakh nebolshikh distantsionno regulyarnykh grafov s massivami peresechenii $\{nm-1, nm-n+m-1,n-m+1;1,1,nm-n+m-1\}$”, Sib. elektron. matem. izv., 16 (2019), 1245–1253 | Zbl

[8] K. Coolsaet, A. Jurishich, “Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs”, J. Comb. Theory, Ser. A, 115 (2008), 1086–1095 | DOI | MR | Zbl