RUS  ENG
Full version
JOURNALS // Vladikavkazskii Matematicheskii Zhurnal // Archive

Vladikavkaz. Mat. Zh., 2021 Volume 23, Number 4, Pages 68–76 (Mi vmj786)

Distance-regular graphs with intersection arrays $\{7,6,6;1,1,2\}$ and $\{42,30,2;1,10,36\}$ do not exist

A. A. Makhneva, V. V. Bitkinab, A. K. Gutnovabc

a N. N. Krasovskii Institute of Mathematics and Mechanics, 16 S. Kovalevskaja St., Ekaterinburg 620990, Russia
b North Ossetian State University, 44–46 Vatutin St., Vladikavkaz 362025, Russia
c North Caucasus Center for Mathematical Research, 19 Vatutin St., Vladikavkaz 362025, Russia

Abstract: Let $\Gamma$ be a distance-regular graph of diameter $3$ without triangles, $u$ be a vertex of the graph $\Gamma$, $\Delta^i =\Gamma_i (u)$ and $\Sigma^i = \Delta^i_{2,3}$. Then $\Sigma^i$ is a regular graph without $3$-cocliques of degree $k'=k_i-a_i-1$ on $v' = k_i$ vertices. Note that for non-adjacent vertices $y, z \in \Sigma^i$ we have $\Sigma^i = \{y, z\} \cup \Sigma^i (y) \cup \Sigma^i (z)$. Therefore, for $\mu'= |\Sigma^i (y) \cap \Sigma^i (z)| $ we have the equality $v'= 2k' + 2-\mu'$. Hence the graph $\Sigma$ is coedge regular with parameters $(v', k', \mu')$. It is proved in the paper that a distance-regular graph with intersection array $\{7,6,6; 1,1,2 \}$ does not exist. In the article by M. S. Nirova "On distance-regular graphs with $\theta_2 = -1$" is proved that if there is a strongly regular graph with parameters $(176,49,12,14)$, in which the neighborhoods of the vertices are $7 \times 7$ -lattices, then there also exists a distance-regular graph with intersection array $\{7,6,6; 1,1,2\}$. M. P. Golubyatnikov noticed that for a distance-regular graph $\Gamma$ with intersection array $\{7,6,6; 1,1,2\}$ graph $\Gamma_2$ is distance regular with intersection array $\{42,30,2; 1,10,36\}$. With this result and calculations of the triple intersection numbers, it is proved that the distance-regular graphs with intersection arrays $\{7,6,6; 1,1,2\}$ and $\{42,30,2; 1,10,36\}$ do not exist.

Key words: distance-regular graph, triangle-free graph, triple intersection numbers.

UDC: 519.17

MSC: 20D45

Received: 14.12.2020

DOI: 10.46698/y2738-1800-0363-i



© Steklov Math. Inst. of RAS, 2025