Distance-Regular Graphs with Intersection Arrays {7,6,6;1,1,2} and {42,30,2;1,10,36} Do not Exist

Makhnev, A. A. , Bitkina, V. V. , Gutnova, A. K.
Vladikavkaz Mathematical Journal 2021. Vol. 23. Issue 4.

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.

Keywords: distance-regular graph, triangle-free graph, triple intersection numbers

Language: Russian Download the full text  

+ References