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