Linear and Multilinear Algebra · 2006 · 24 citations · 7 references
Natural SciencesComputer ScienceMathematicsCombinatoricsComputational GeometryTopologyApproximation AlgorithmsEigenvalue ProblemsGraph AlgorithmsGraph Theory
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. 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 the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.
7
Three-Class Association Schemes
Edwin van Dam · Journal of Algebraic Combinatorics · 1999 · 103 citations · Full text
Deza graphs: A generalization of strongly regular graph
Martin Erickson, S. Fernando, Willem H. Haemers et al. · Journal of Combinatorial Designs · 1999 · 70 citations · Full text