Regular graphs with four eigenvalues. (English) Zbl 0839.05072

Connected regular graphs having at most three distinct eigenvalues are the complete and the strongly regular graphs. Distance-regular graphs of diameter \(d\) are generalizations of complete \((d= 1)\) and strongly regular \((d= 2)\) graphs. The present paper studies the connected regular graphs with four distinct eigenvalues. Properties and feasibility conditions of the eigenvalues are presented. The paper also gives several constructions, some characterizations, and uniqueness and nonexistence results.
Reviewer: W.K.Chen (Chicago)


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C75 Structural characterization of families of graphs
05E30 Association schemes, strongly regular graphs
Full Text: DOI


[1] Brouwer, A.E.; Cohen, A.M.; Neumaier, A., Distance-regular graphs, () · Zbl 0747.05073
[2] Brouwer, A.E.; Haemers, W.H., The gewirtz graph: an exercise in the theory of graph spectra, Eur. J. combinatorics, 14, 397-407, (1993) · Zbl 0794.05076
[3] Brouwer, A.E.; van Lint, J.H., Strongly regular graphs and partial geometries, (), 85-122 · Zbl 0555.05016
[4] Bussemaker, F.C.; Cvetković, D.M.; Seidel, J.J., Graphs related to exceptional root systems, (), 185-191 · Zbl 0392.05055
[5] Cameron, P.J.; Goethals, J.M.; Seidel, J.J., Strongly regular graphs having strongly regular subconstituents, J. algebra, 55, 257-280, (1978) · Zbl 0444.05045
[6] Cvetković, D.M.; Doob, M.; Sachs, H., Spectra of graphs, (1979), V.E.B. Deutscher Verlag der Wissenschaften Berlin
[7] Doob, M., Graphs with a small number of distinct eigenvalues, Ann. N.Y. acad. sci., 175, 104-110, (1970) · Zbl 0241.05112
[8] Doob, M., On characterizing certain graphs with four eigenvalues by their spectra, Linear algebra appl., 3, 461-482, (1970) · Zbl 0202.55703
[9] Doob, M.; Cvetković, D.M., On spectral characterizations and embeddings of graphs, Linear algebra appl., 27, 17-26, (1979) · Zbl 0417.05025
[10] Gilbert, W.J., Modern algebra with applications, (1976), Wiley New York · Zbl 0346.00001
[11] Godsil, C.D.; McKay, B.D., Feasibility conditions for the existence of walk-regular graphs, Linear algebra appl., 30, 51-61, (1980) · Zbl 0452.05045
[12] Haemers, W.H., Eigenvalue techniques in design and graph theory, () · Zbl 0429.05013
[13] W. H. Haemers, Distance-regularity and the spectrum of graphs, Linear Algebra Appl., to appear.
[14] Haemers, W.H.; Higman, D.G., Strongly regular graphs with strongly regular decomposition, Linear algebra appl., 114/115, 379-398, (1989) · Zbl 0719.05069
[15] W. H. Haemers and E. Spence, Graphs cospectral with distance-regular graphs, Linear Multilin. Alg., to appear. · Zbl 0831.05045
[16] Hoffman, A.J., On the polynomial of a graph, Am. math. monthly, 70, 30-36, (1963) · Zbl 0112.14901
[17] Hollmann, H.D.L., Association schemes, () · Zbl 1136.94324
[18] Hollmann, H., Pseudocyclic 3-class association schemes on 28 points, Discrete math., 52, 209-224, (1984) · Zbl 0559.05019
[19] Mathon, R., 3-class association schemes, (), 123-155
[20] Paulus, A.J.L., ()
[21] Seidel, J.J., Strongly regular graphs, (), 157-180, Cambridge · Zbl 0431.05018
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.