Pseudo-Geometric Strongly Regular Graphs with a Regular Point

Abstract

We study pseudo-geometric strongly regular graphs whose second subconstituent with respect to a vertex is a cover of a strongly regular graph or a complete graph. By studying the structure of such graphs, we characterize all graphs containing such a vertex, and use our characterization to find many new strongly regular graphs. Thereby, we answer a question posed by Gardiner, Godsil, Hensel, and Royle. We give an explicit construction for q new, pairwise non-isomorphic graphs with the same parameters as the collinearity graph of generalized quadrangles of order $(q,q)$ and a new non-geometric graph with the same parameters as the collinearity graph of the Hermitian generalized quadrangle of order $(q^2,q)$, for prime powers $q$. Using our characterization, we computed 135478 new strongly regular graphs with parameters (85,20,3,5) and 27 039 strongly regular graphs with parameters (156, 30, 4, 6).

22 pages, 4 figures