Geodesic
On distance-regular graphs with $c_2=2$
Diskretnaya Matematika, Tome 32 (2020) no. 1, pp. 74-80.

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

Let $\Gamma$ be a distance-regular graph of diameter 3 with $c_2=2$ (any two vertices with distance 2 between them have exactly two common neighbors). Then the neighborhood $\Delta$ of the vertex $w$ in $\Gamma$ is a partial line space. In view of the Brouwer–Neumaier result either $\Delta$ is the union of isolated $(\lambda+1)$-cliques or the degrees of vertices $k\ge \lambda(\lambda+3)/2$, and in the case of equality $k=5, \lambda=2$ and $\Gamma$ is the icosahedron graph. A. A. Makhnev, M. P. Golubyatnikov and Wenbin Guo have investigated distance-regular graphs $\Gamma$ of diameter 3 such that $\bar \Gamma_3$ is the pseudo-geometrical network graph. They have found a new infinite set $\{2u^2-2m^2+4m-3,2u^2-2m^2,u^2-m^2+4m-2;1,2,u^2-m^2\}$ of feasible intersection arrays for such graphs with $c_2=2$. Here we prove that some distance-regular graphs from this set do not exist. It is proved also that distance-regular graph with intersection array $\{22,16,5;1,2,20\}$ does not exist.
Keywords: distance-regular graph, partial line space, graph with $c_2=2$. 
@article{DM_2020_32_1_a5,
     author = {A. A. Makhnev and M. S. Nirova},
     title = {On distance-regular graphs with $c_2=2$},
     journal = {Diskretnaya Matematika},
     pages = {74--80},
     publisher = {mathdoc},
     volume = {32},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2020_32_1_a5/}
}
TY  - JOUR
AU  - A. A. Makhnev
AU  - M. S. Nirova
TI  - On distance-regular graphs with $c_2=2$
JO  - Diskretnaya Matematika
PY  - 2020
SP  - 74
EP  - 80
VL  - 32
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2020_32_1_a5/
LA  - ru
ID  - DM_2020_32_1_a5
ER  - 
%0 Journal Article
%A A. A. Makhnev
%A M. S. Nirova
%T On distance-regular graphs with $c_2=2$
%J Diskretnaya Matematika
%D 2020
%P 74-80
%V 32
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2020_32_1_a5/
%G ru
%F DM_2020_32_1_a5
A. A. Makhnev; M. S. Nirova. On distance-regular graphs with $c_2=2$. Diskretnaya Matematika, Tome 32 (2020) no. 1, pp. 74-80. http://geodesic.mathdoc.fr/item/DM_2020_32_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.L. Gavrilyuk, A.A. Makhnev, “Ob avtomorfizmakh distantsionno regulyarnykh grafov s massivom peresechenii $\{56,45,1;1,9,56\}$”, Doklady Akademii nauk, 432:5 (2010), 512–515

[3] A.E. Brouwer, A. Neumaier, “A remark on partial linear spaces with girth 5 with an application to strongly regular graphs”, Combinatorica, 8 (1998), 57–61 | DOI | MR

[4] A.E. Brouwer, S Sumaloj, C. Worawannotai, “The nonexistence of distance-regular graphs with intersection arrays $\{27,20,10;1,2,18\}$ and $\{36,28,4;1,2,24\}$”, Australasian J. Comb., 66:2 (2016), 330–332 | MR | Zbl

[5] A.A. Makhnev, M.P. Golubyatnikov, “A Shilla graph with intersection array $\{12,10,2;1,2,8\}$ does not exist”, Math. Notes, 106:5 (2019), 850–853 | DOI | DOI | MR

[6] V.I. Belousova, A.A. Makhnev, “Avtomorfizmy distantsionno regulyarnogo grafa s massivom peresechenii $\{30,27,24;1,2,10\}$”, Sibirskie elektron. matem. izvestiya, 16 (2019), 493–500 | MR | Zbl

[7] A.A. Makhnev, M.M. Khamgokova, “Avtomorfizmy distantsionno regulyarnogo grafa s massivom peresechenii $\{39,36,22;1,2,18\}$”, Sibirskie elektron. matem. izvestiya, 16 (2019), 638–647 | MR | Zbl

[8] A.A. Makhnev, A.A. Tokbaeva, “O distantsionno regulyarnom grafe s massivom peresechenii $\{35,28,6;1,2,30\}$”, Vladikavkazskii matem. zhurnal, 21:2 (2019), 27–37 | MR

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