Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Exceptional graphs with smallest eigenvalue $ -2$ and related problems


Authors: F. C. Bussemaker and A. Neumaier
Journal: Math. Comp. 59 (1992), 583-608
MSC: Primary 05C50
DOI: https://doi.org/10.1090/S0025-5718-1992-1134718-6
MathSciNet review: 1134718
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] H. F. Baker, A locus with 25920 linear self-transformations, Cambridge Tracts in Math. and Math. Physics, vol. 39, Cambridge Univ. Press, London, 1946. MR 0019327 (8:400b)
  • [2] E. Bannai and T. Ito, Algebraic combinatorics. I: Association schemes, Benjamin-Cummings Lecture Note Series, vol. 58, Benjamin/Cummings, London, 1984. MR 882540 (87m:05001)
  • [3] L. W. Beineke, Derived graphs and digraphs, Beiträge zur Graphentheorie (H. Sachs et al., eds.), Teubner, Leipzig, 1968, pp. 17-33.
  • [4] N. L. Biggs, Algebraic graph theory, Cambridge Tracts in Math., vol. 67, Cambridge Univ. Press, Cambridge, 1974. MR 0347649 (50:151)
  • [5] A. Blokhuis and A. E. Brouwer, Classification of the locally 4-by-4 grid graphs, Math. Centr. Report PM-R8401, Amsterdam, 1984.
  • [6] A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance regular graphs, Springer, Berlin, 1989. MR 1002568 (90e:05001)
  • [7] A. E. Brouwer and A. Neumaier, The graphs with largest eigenvalue between 2 and $ \sqrt {2 + \sqrt 2 } $, Linear Algebra Appl. 114/115 (1989), 273-276. MR 986880 (90f:05094)
  • [8] F. C. Bussemaker, D. H. Cvetković, and J. J. Seidel, Graphs related to exceptional root systems, Report TH Eindhoven 76-WSK-05, 1976.
  • [9] F. C. Bussemaker, R. A. Mathon, and J. J. Seidel, Tables of two-graphs, Combinatorics and Graph Theory (S. B. Rao, ed.), Lecture Notes in Math., vol. 885, Springer, 1981, pp. 70-112. (Full details in Report 79-WSK-05, Technische Hogeschool Eindhoven, 1979.) MR 655610 (84b:05055)
  • [10] P. J. Cameron, J. M. Goethals, J. J. Seidel, and E. E. Shult, Line graphs, root systems and elliptic geometry, J. Algebra 43 (1976), 305-327. MR 0441787 (56:182)
  • [11] Lie-Chien Chang, The uniqueness and non-uniqueness of the triangular association scheme, Sci. Record Peking Math. (New Ser.) 3 (1959), 604-613. MR 0117167 (22:7950)
  • [12] L. C. Chang, Association schemes of partially balanced block designs with parameters $ n = 28, {n_1} = 12, {n_2} = 15$ and $ p_{11}^2 = 4$, Sci. Record Peking Math. (New Ser.) 4 (1960), 12-18.
  • [13] M. Chein, Recherche des graphes des matrices de Coxeter hyperboliques d'ordre $ \leq 10$, Rev. Française Informat. Recherche Opérationnelle 3 (1969), 3-16. MR 0294181 (45:3254)
  • [14] F. H. Clarke, A graph polynomial and its application, Discrete Math. 3 (1972), 305-315. MR 0318003 (47:6552)
  • [15] H. S. M. Coxeter, Extreme forms, Canad. J. Math. 3 (1951), 391-441. MR 0044580 (13:443c)
  • [16] D.M. Cvetković, M. Doob, and I. Gutman, On graphs whose spectral radius does not exceed $ \sqrt {2 + \sqrt 5 } $, Ars Combinatoria 14 (1982), 225-239. MR 683990 (84i:05076)
  • [17] D. M. Cvetković, M. Doob, and H. Sachs, Spectra of graphs, V. E. B. Deutscher Verlag der Wissenschaften, Berlin, 1979. (Also, Academic Press, New York, 1980.) MR 572262 (81i:05054)
  • [18] D. M. Cvetković, M. Doob, and S. Simić, Generalized line graphs, J. Graph Theory 5 (1981), 385-399. MR 635701 (82k:05091)
  • [19] M. Doob, An interrelation between line graphs, eigenvalues, and matroids, J. Combin. Theory Ser. B 15 (1973), 40-50. MR 0439687 (55:12573)
  • [20] -, A surprising property of the least eigenvalue of a graph, Linear Algebra Appl. 46 (1982), 1-7. MR 664691 (83m:05097)
  • [21] M. Doob and D. Cvetković, On spectral characterizations and embeddings of graphs, Linear Algebra Appl. 27 (1979), 17-26. MR 545719 (81d:05050)
  • [22] Y. Egawa, Characterization of $ H(n,q)$ by the parameters, J. Combin. Theory Ser. A 31 (1981), 108-125. MR 629586 (82k:05092)
  • [23] F. Goodman, P. de la Harpe, and V. Jones, Dynkin diagrams and towers of algebras, Chapter 1: Matrices over natural numbers, Preprint, Genève, 1986.
  • [24] H. Hiller, Geometry of Coxeter groups, Research Notes in Math., Pitman, New York, 1982. MR 649068 (83h:14045)
  • [25] A. J. Hoffman, On eigenvalues and colourings of graphs, Graph Theory and its Applications (B. Harris, ed.), Academic Press, New York, 1970, pp. 79-91. MR 0284373 (44:1601)
  • [26] -, On graphs whose least eigenvalue exceeds $ - 1 - \sqrt 2 $, Linear Algebra Appl. 16 (1977), 153-166. MR 0469826 (57:9607)
  • [27] -, On limit points of spectral radii of nonnegative symmetric integral matrices, Graph Theory and Applications (Y. Alavi et al., eds.), Lecture Notes in Math., vol. 303, Springer, 1972, pp. 165-172. MR 0347860 (50:361)
  • [28] 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 0014037 (7:233c)
  • [29] J. L. Koszul, Lectures on hyperbolic Coxeter groups, Dept. Math., Univ. Notre Dame, 1967.
  • [30] Vijaya Kumar, S. B. Rao, and N. M. Singhi, Graphs with eigenvalues at least $ - 2$, Linear Algebra Appl. 46 (1982), 27-42. MR 664693 (83m:05099)
  • [31] P. W. H. Lemmens and J. J. Seidel, Equiangular lines, J. Algebra 24 (1973), 494-512. MR 0307969 (46:7084)
  • [32] G. A. Miller, H. F. Blichfeldt, and L. E. Dickson, Theory and applications of finite groups, Part III, reprint, Dover, New York, 1961. MR 0123600 (23:A925)
  • [33] A. Neumaier, Lattices of simplex type, SIAM J. Alg. Discrete Math. 4 (1983), 145-160. MR 699768 (85f:05040)
  • [34] -, Characterization of a class of distance regular graphs, J. Reine Angew. Math. 357 (1985), 182-192. MR 783540 (86f:05109)
  • [35] S. B. Rao, N. M. Singhi, and K. S. Vijayan, The minimal forbidden subgraphs for generalized line graphs, Combinatorics and Graph Theory (S. B. Rao, ed.), Lecture Notes in Math., vol. 885, Springer, 1981, pp. 459-472. MR 655644 (83i:05062)
  • [36] J. J. Seidel, Strongly regular graphs with $ ( - 1,1,0)$ adjacency matrix having eigenvalue 3, Linear Algebra Appl. 1 (1968), 281-298. MR 0234861 (38:3175)
  • [37] S. S. Shrikhande, The uniqueness of the $ {L_2}$ association scheme, Ann. Math. Statist. 30 (1959), 781-798. MR 0110166 (22:1048)
  • [38] J. H. Smith, Some properties of the spectrum of a graph, Combinatorial Structures and Their Applications (R. Guy, ed.), Gordon and Breach, New York, 1970, pp. 403-406. MR 0266799 (42:1702)
  • [39] D. E. Taylor, Regular 2-graphs, Proc. London Math. Soc. (3) 34 (1977), 257-274. MR 0476587 (57:16147)
  • [40] P. Terwilliger, Distance-regular graphs with girth 3 or 4. I, J. Combin. Theory Ser. B 39 (1985), 265-281. MR 815396 (87g:05198)
  • [41] -, A class of distance-regular graphs that are Q-polynomial, J. Combin. Theory Ser. B 40 (1986), 213-223. MR 838220 (87g:05199)
  • [42] -, Root systems and the Johnson and Hamming graphs, European J. Combin. 8 (1987), 73-102. MR 884067 (88d:05147)
  • [43] -, A new feasibility condition for distance regular graphs. Discrete Math. 61 (1986), 311-315. MR 855336 (87i:05142)
  • [44] G. R. Vijayakumar, A characterization of generalized line graphs and classification of graphs with eigenvalues at least $ - 2$, J. Combin. Inform. System Sci. (to appear). MR 959067 (89g:05055)
  • [45] E. Witt, Spiegelungsgruppen und Aufzählung halbeinfacher Liescher Ringe, Abh. Math. Sem. Hansischen Univ. 14 (1941), 289-322. MR 0005099 (3:100f)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 05C50

Retrieve articles in all journals with MSC: 05C50


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1992-1134718-6
Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society