Exceptional graphs with smallest eigenvalue -2 and related problems

Bussemaker, F. C.; Neumaier, A.

doi:10.1090/S0025-5718-1992-1134718-6

Exceptional graphs with smallest eigenvalue $-2$ and related problems
HTML articles powered by AMS MathViewer

by F. C. Bussemaker and A. Neumaier PDF

Math. Comp. 59 (1992), 583-608 Request permission

Abstract:

This paper summarizes the known results on graphs with smallest eigenvalue around $- 2$, and completes the theory by proving a number of new results, giving comprehensive tables of the finitely many exceptions, and posing some new problems. Then the theory is applied to characterize a class of distance-regular graphs of large diameter by their intersection array.

References

H. F. Baker, A Locus with $25920$ Linear Self-Transformations, Cambridge Tracts in Mathematics and Mathematical Physics, No. 39, Cambridge, at the University Press; New York, The Macmillan Company, 1946. MR 0019327
Eiichi Bannai and Tatsuro Ito, Algebraic combinatorics. I, The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1984. Association schemes. MR 882540

Derived graphs and digraphs

Norman Biggs, Algebraic graph theory, Cambridge Tracts in Mathematics, No. 67, Cambridge University Press, London, 1974. MR 0347649

Classification of the locally

by

grid graphs

A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-regular graphs, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 18, Springer-Verlag, Berlin, 1989. MR 1002568, DOI 10.1007/978-3-642-74341-2
A. E. Brouwer and A. Neumaier, The graphs with spectral radius between $2$ and $\sqrt {2+\sqrt {5}}$, Linear Algebra Appl. 114/115 (1989), 273–276. MR 986880, DOI 10.1016/0024-3795(89)90466-7

Graphs related to exceptional root systems

F. C. Bussemaker, R. A. Mathon, and J. J. Seidel, Tables of two-graphs, Combinatorics and graph theory (Calcutta, 1980) Lecture Notes in Math., vol. 885, Springer, Berlin-New York, 1981, pp. 70–112. MR 655610
P. J. Cameron, J.-M. Goethals, J. J. Seidel, and E. E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra 43 (1976), no. 1, 305–327. MR 441787, DOI 10.1016/0021-8693(76)90162-9
Chang Li-ch’ien, The uniqueness and nonuniqueness of the triangular association schemes, Sci. Record (N.S.) 3 (1959), 604–613. MR 117167

Association schemes of partially balanced block designs with parameters

and

4

M. Chein, Recherche des graphes des matrices de Coxeter hyperboliques d’ordre $\leq \,10$, Rev. Française Informat. Recherche Opérationnelle 3 (1969), no. Sér. R-3, 3–16 (French). MR 0294181
Frank H. Clarke, A graph polynomial and its applications, Discrete Math. 3 (1972), 305–313. MR 318003, DOI 10.1016/0012-365X(72)90088-X
H. S. M. Coxeter, Extreme forms, Canad. J. Math. 3 (1951), 391–441. MR 44580, DOI 10.4153/cjm-1951-045-8
Dragoš Cvetković, Michael Doob, and Ivan Gutman, On graphs whose spectral radius does not exceed $(2+\sqrt {5})^{1/2}$, Ars Combin. 14 (1982), 225–239. MR 683990
Dragoš M. Cvetković, Michael Doob, and Horst Sachs, Spectra of graphs, Pure and Applied Mathematics, vol. 87, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. Theory and application. MR 572262
Dragoš Cvetković, Michael Doob, and Slobodan Simić, Generalized line graphs, J. Graph Theory 5 (1981), no. 4, 385–399. MR 635701, DOI 10.1002/jgt.3190050408
Michael Doob, An interrelation between line graphs, eigenvalues, and matroids, J. Combinatorial Theory Ser. B 15 (1973), 40–50. MR 439687, DOI 10.1016/0095-8956(73)90030-0
Michael Doob, A surprising property of the least eigenvalue of a graph, Linear Algebra Appl. 46 (1982), 1–7. MR 664691, DOI 10.1016/0024-3795(82)90021-0
Michael Doob and Dragoš Cvetković, On spectral characterizations and embeddings of graphs, Linear Algebra Appl. 27 (1979), 17–26. MR 545719, DOI 10.1016/0024-3795(79)90028-4
Yoshimi Egawa, Characterization of $H(n,\,q)$ by the parameters, J. Combin. Theory Ser. A 31 (1981), no. 2, 108–125. MR 629586, DOI 10.1016/0097-3165(81)90007-8

Dynkin diagrams and towers of algebras

Matrices over natural numbers

Howard Hiller, Geometry of Coxeter groups, Research Notes in Mathematics, vol. 54, Pitman (Advanced Publishing Program), Boston, Mass.-London, 1982. MR 649068
Alan J. Hoffman, On eigenvalues and colorings of graphs, Graph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, Wis., 1969) Academic Press, New York, 1970, pp. 79–91. MR 0284373
A. J. Hoffman, On graphs whose least eigenvalue exceeds $-1-\sqrt {2}$, Linear Algebra Appl. 16 (1977), no. 2, 153–165. MR 469826, DOI 10.1016/0024-3795(77)90027-1
Alan J. Hoffman, On limit points of spectral radii of non-negative symmetric integral matrices, Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), Lecture Notes in Math., Vol. 303, Springer, Berlin, 1972, pp. 165–172. MR 0347860
Q. M. Husain, On the totality of the solutions for the symmetrical incomplete block designs: $\lambda =2, k=5$ or $6$, Sankhyā 7 (1945), 204–208. MR 14037

Lectures on hyperbolic Coxeter groups

Vijaya Kumar, S. B. Rao, and N. M. Singhi, Graphs with eigenvalues at least $-2$, Linear Algebra Appl. 46 (1982), 27–42. MR 664693, DOI 10.1016/0024-3795(82)90023-4
P. W. H. Lemmens and J. J. Seidel, Equiangular lines, J. Algebra 24 (1973), 494–512. MR 307969, DOI 10.1016/0021-8693(73)90123-3
G. A. Miller, H. F. Blichfeldt, and L. E. Dickson, Theory and applications of finite groups, Dover Publications, Inc., New York, 1961. MR 0123600
A. Neumaier, Lattices of simplex type, SIAM J. Algebraic Discrete Methods 4 (1983), no. 2, 145–160. MR 699768, DOI 10.1137/0604017
A. Neumaier, Characterization of a class of distance regular graphs, J. Reine Angew. Math. 357 (1985), 182–192. MR 783540, DOI 10.1515/crll.1985.357.182
S. B. Rao, N. M. Singhi, and K. S. Vijayan, The minimal forbidden subgraphs for generalized line-graphs, Combinatorics and graph theory (Calcutta, 1980) Lecture Notes in Math., vol. 885, Springer, Berlin-New York, 1981, pp. 459–472. MR 655644
J. J. Seidel, Strongly regular graphs with $(-1,\,1,\,0)$ adjacency matrix having eigenvalue $3$, Linear Algebra Appl. 1 (1968), 281–298. MR 234861, DOI 10.1016/0024-3795(68)90008-6
S. S. Shrikhande, The uniqueness of the $L_{2}$ association scheme, Ann. Math. Statist. 30 (1959), 781–798. MR 110166, DOI 10.1214/aoms/1177706207
John H. Smith, Some properties of the spectrum of a graph, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) Gordon and Breach, New York, 1970, pp. 403–406. MR 0266799
D. E. Taylor, Regular $2$-graphs, Proc. London Math. Soc. (3) 35 (1977), no. 2, 257–274. MR 476587, DOI 10.1112/plms/s3-35.2.257
Paul Terwilliger, Distance-regular graphs with girth $3$ or $4$. I, J. Combin. Theory Ser. B 39 (1985), no. 3, 265–281. MR 815396, DOI 10.1016/0095-8956(85)90054-1
Paul Terwilliger, A class of distance-regular graphs that are $Q$-polynomial, J. Combin. Theory Ser. B 40 (1986), no. 2, 213–223. MR 838220, DOI 10.1016/0095-8956(86)90078-X
Paul Terwilliger, Root systems and the Johnson and Hamming graphs, European J. Combin. 8 (1987), no. 1, 73–102. MR 884067, DOI 10.1016/S0195-6698(87)80023-9
Paul Terwilliger, A new feasibility condition for distance-regular graphs, Discrete Math. 61 (1986), no. 2-3, 311–315. MR 855336, DOI 10.1016/0012-365X(86)90102-0
G. K. Vijayakumar, A characterization of generalized line graphs and classification of graphs with eigenvalues at least $2$, J. Combin. Inform. System Sci. 9 (1984), no. 3, 182–192. MR 959067
Ernst Witt, Spiegelungsgruppen und Aufzählung halbeinfacher Liescher Ringe, Abh. Math. Sem. Hansischen Univ. 14 (1941), 289–322 (German). MR 5099, DOI 10.1007/BF02940749