|
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.
Received: 14.12.2020
Citation:
A. A. Makhnev, V. V. Bitkina, A. K. Gutnova, “Distance-regular graphs with intersection arrays $\{7,6,6;1,1,2\}$ and $\{42,30,2;1,10,36\}$ do not exist”, Vladikavkaz. Mat. Zh., 23:4 (2021), 68–76
Linking options:
https://www.mathnet.ru/eng/vmj786 https://www.mathnet.ru/eng/vmj/v23/i4/p68
|
|