On graphs whose vertex neighborhoods are locally pseudocyclic graphs

V. Kabanov,   A. Makhnev

A locally pseudocyclic graph is a strongly regular graph with $\lambda=2$. We study the distance-regular graphs whose vertex neighborhoods are locally pseudocyclic graphs.

In [1], a program is proposed for the study of distance-regular graphs whose vertex neighborhoods are strongly regular graphs 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.

In the present work, we study completely regular graphs whose vertex neighborhoods are locally pseudocyclic graphs with eigenvalue 3.

Theorem. Let $\Gamma$ be a completely regular graph whose vertex neighborhoods are locally pseudocyclic graphs with nonprincipal eigenvalue $3$. Then either $d(\Gamma)\ge 4$, the vertex neighborhoods are strongly regular graphs with parameters $(96,19,2,4)$ and $\mu=12,16$, or $d(\Gamma)=3$ and one of the following holds:

$(1)$ the vertex neighborhoods are strongly regular graphs with parameters $(96,19,2,4)$ and $\mu=12,16,19,24,32$;

$(2)$ the vertex neighborhoods are strongly regular graphs with parameters $(196,39,2,9)$ and $\mu=42,48,52,56$;

$(3)$ the vertex neighborhoods are strongly regular graphs with parameters $(256,51,2,12)$ and $\mu=48,51,64,68,96$.

Corollary. A distance-regular graphs whose vertex neighborhoods are pseudocyclic graphs with eigenvalue $3$ has intersection array $\{96,76,1;1,19,96\}$ or $\{256,204,1;1,51,256\}$.

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. А. Makhnev, On strongly regular graphs with eigenvalue 3 and their extensions, Dokl. Akad. Nauk, 451, N5 (2013), 475–478. (Russian)

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