zbMATH — the first resource for mathematics

On quasi-strongly regular graphs. (English) Zbl 1108.05097
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 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.

05E30 Association schemes, strongly regular graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A42 Inequalities involving eigenvalues and eigenvectors
Zbl 0159.25403
Full Text: DOI
[1] Bannai E, Proceedings of Symposia Pure Mathematics 47 pp 343– (1987)
[2] Bose R, Pacific Journal of Mathematics 13 pp 389– (1963)
[3] Brouwer AE, Distance-regular graphs 3 (1989)
[4] Cameron, PJ. http://www.maths.qmw.ac.uk/ pjc/papers.html
[5] DOI: 10.1023/A:1018628204156 · Zbl 0929.05096
[6] DOI: 10.1002/(SICI)1520-6610(1999)7:6<395::AID-JCD1>3.0.CO;2-U · Zbl 0959.05122
[7] Godsil C, Algebraic Combinatorics (1993)
[8] Golightly W, Congressus Numerantium 124 pp 89– (1997)
[9] Golightly W, Bulletin of the Institute of Combinatorics and its Applications 24 pp 51– (1998)
[10] DOI: 10.1023/A:1026544111089 · Zbl 0959.05121
[11] DOI: 10.1016/S0012-365X(02)00560-5 · Zbl 1014.05076
[12] Neumaier, A. 1981.On a class of edge-regular graphs, Edited by: Aigner, M and Jungnickel, D. 223–230. Berlin: Springer-Verlag. Geometries and Groups (Proceedings, Berlin 1981), Volume 893 of Lecture Notes in Mathematics · Zbl 0499.05035
[13] DOI: 10.1016/S0012-365X(02)00560-5 · Zbl 1014.05076
[14] DOI: 10.1016/0024-3795(68)90008-6 · Zbl 0159.25403
[15] Taylor DE, Combinatorial Mathematics pp 313– (1977)
[16] DOI: 10.1016/0012-365X(82)90025-5 · Zbl 0495.05045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.