05126287

j

05126287 Goldberg, Felix On quasi-strongly regular graphs. Linear Multilinear Algebra 54, No. 6, 437-451 (2006). 2006 Taylor \& Francis, Abingdon EN distance regular graph adjacency eigenvalues spectral gap feasibility conditions Zbl 0159.25403

doi:10.1080/03081080600867210

Summary: We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a ``spectral gap''-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph [see {\it J. J. Seidel}, Linear Algebra Appl. 1, 281--298 (1968; Zbl 0159.25403)]. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a ``lower-order approximation'' to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.