ISSN 1683-3414 (Print)   •   ISSN 1814-0807 (Online)
   Log in


Address: Markusa st. 22, Vladikavkaz,
362027, RNO-A, Russia
Phone: (8672)50-18-06





DOI: 10.46698/y2738-1800-0363-i

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.
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  
For citation: Makhnev, A. A., Bitkina, V. V. and Gutnova, A. K. Distance-Regular Graphs with Intersection Arrays† {7,6,6;1,1,2} and {42,30,2;1,10,36} Do not Exist, Vladikavkaz Math. J., 2021, vol. 23, no. 3, pp.68-76 (in Russian). DOI 10.46698/y2738-1800-0363-i
+ References

← Contents of issue
  | Home | Editorial board | Publication ethics | Peer review guidelines | Current | Archive | Rules for authors |  
© 1999-2022 ёжный математический институт