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

Diskr. Mat., 2020 Volume 32, Issue 1, Pages 74–80 (Mi dm1595)

This article is cited in 1 paper

On distance-regular graphs with $c_2=2$

A. A. Makhnevab, M. S. Nirovaab

a Institute of Mathematics and Mechanics UB RAS
b Kabardino-Balkarskii State University

Abstract: 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$.

UDC: 519.172

Received: 24.10.2019

DOI: 10.4213/dm1595


 English version:
Discrete Mathematics and Applications, 2021, 31:6, 397–401

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025