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

+ References

The sole copyright holder of the published work is the Founder of the Vladikavkaz Mathematical Journal. The terms of use of this work are governed by an open license (Creative Commons Attribution-NonCommercial 4.0 International). The use of metadata of the scientific article, including the title, abstract, author information, references, identifiers, and other bibliographic description elements for subsequent unrestricted use, is carried out under the terms of the CC BY or CC0 open licenses.