On graphs whose vertex neighborhoods are strongly regular
with parameters \((196,45,4,12)\)

A. Makhnev,  A. Tokbaeva

The paper [1] proposes a program for the study of distance-regular graphs whose vertex neigborhoods are strongly regular with eigenvalue \(3\). In [1], there is also a reduction of the problem to the case where the vertex neighborhoods belong to a finite set of exceptional graphs. The parameters of the exceptional strongly regular graphs with nonprincipal eigenvalue \(3\) are found in [2]. In particular, the graph with \(\lambda=4\) has parameters \((196,45,4,12)\). In the present work, we study the completely regular graphs whose vertex neighborhoods are strongly regular with parameters \((196,45,4,12)\).

Theorem. Let \(\Gamma\) be a completely regular graph whose vertex neighborhoods are strongly regular graphs with parameters \((196,45,4,12)\), let \(u\) be a vertex of \(\Gamma\), and let \(k_i=|\Gamma_i(u)|\). Then \(d(\Gamma)=3\) and one of the following holds:

\((1)\) \(\mu=42\), \(2\le k_3\le 46\);

\((2)\) \(\mu=49\), \(2\le k_3\le 42\);

\((3)\) \(\mu=50\), \(2\le k_3\le 36\).

Corollary. The graph whose vertex neighborhoods are strongly regular graphs with parameters \((196,45,4,12)\) is not distance-regular.

Acknowledgement. The work is partially supported by RFBR (grants 12-01-00012), RFBR – NSFC of China (grant 12-01-91155), by the Program of the Department of Mathematical Sciences of RAS (project 12-T-1-1003), and by the Joint Research Program of UB RAS with SB RAS (project 12-C-1-1018) and with NAS of Belarus (project 12-C-1-1009).

References

1. A. A. Makhnev, On strongly regular graphs with eigenvalue \(3\) and their extensions, Dokl. Akad. Nauk 451, N5 (2013), 475–478. (Russian)
2. A. A. Makhnev, D. V. Paduchikh, Exceptional strongly regular graphs with eigenvalue \(3\) and their extensions, Internat. Conf. "Algebra and Combinatorics", Abst., Ekaterinburg (2013), 67–69. (Russian)

See also the authors' pdf version (in Russian):