On graphs whose vertex neighborhoods are strongly regular
with parameters \((111,30,5,9)\) or \((169,42,5,12)\)

A. Kagazezheva,   A. Makhnev

The paper [1] begins the study of graphs whose vertex neighborhoods are strongly regular graphs with nonprincipal eigenvalue \(3\). Namely, the problem is reduced to the study of graphs whose vertex neighborhoods are exceptional strongly regular graphs with nonprincipal eigenvalue \(3\). The parameters of the exceptional strongly regular graphs with nonprincipal eigenvalue \(3\) are found in [2]. In particular, the graph with \(\lambda=5\) has parameters \((21,10,5,4)\), \((111,30,5,9)\), or \((169,42,5,12)\). In the present work, we study the completely regular graphs whose vertex neighborhoods are strongly regular with the specified parameters.

Theorem 1. Let \(\Gamma\) be a completely regular graph whose vertex neighborhoods are strongly regular graphs with parameters \((111,30,5,9)\), let \(u\) be a vertex of \(\Gamma\), and let \(k_i=|\Gamma_i(u)|\). Then \(d(\Gamma)=3\), \(k_3\) is even, and one of the following holds:

\((1)\) \(\mu=30\), \(2\le k_3\le 18\);

\((2)\) \(\mu=40\), \(2\le k_3\le 6\), and \(\Gamma_3\) is the union of isolated vertices and edges.

Theorem 2. Let \(\Gamma\) be a completely regular graph whose vertex neighborhoods are strongly regular graphs with parameters \((169,42,5,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=39\), \(k_3\) is even, and \(2\le k_3\le 42\);

\((1)\) \(\mu=42\), \(k_3\) is odd, and \(3\le k_3\le 33\);

\((3)\) \(\mu=63\), \(k_3\) is even, \(2\le k_3\le 12\), and \(\Gamma_3\) is the union of isolated vertices and edges.

Corollary. Let \(\Gamma\) be a distance-regular graph whose vertex neighborhoods are strongly regular graphs with eigenvalue \(3\) and parameters \((v',k',5,\mu')\). Then the vertex neighborhoods are either isomorphic to the triangular graph \(T(7)\) and \(\Gamma\) is the half-graph of the \(7\)-cube, or strongly regular with parameters \((169,42,5,12)\) and \(\Gamma\) has intersection array \(\{169,126,1;1,42,169\}\).

Acknowledgement. The work is partially supported by RFBR (grants 12-01-00012), 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):