Exceptional graphs with smallest eigenvalue -2 and related problems. (English) Zbl 0770.05060
Math. Comput. 59, No. 200, 583-608 (1992); Microfiche Suppl.
Authors’ 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.
Reviewer: R.L.Hemminger (Nashville)
MSC:
| 05C35 | Extremal problems in graph theory |
| 05E99 | Algebraic combinatorics |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C12 | Distance in graphs |
References:
| [1] | 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. · Zbl 0063.00170 |
| [2] | Eiichi Bannai and Tatsuro Ito, Algebraic combinatorics. I, The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1984. Association schemes. · Zbl 0555.05019 |
| [3] | L. W. Beineke, Derived graphs and digraphs, Beiträge zur Graphentheorie , Teubner, Leipzig, 1968, pp. 17-33. · Zbl 0179.29204 |
| [4] | Norman Biggs, Algebraic graph theory, Cambridge University Press, London, 1974. Cambridge Tracts in Mathematics, No. 67. · Zbl 0284.05101 |
| [5] | A. Blokhuis and A. E. Brouwer, Classification of the locally 4-by-4 grid graphs, Math. Centr. Report PM-R8401, Amsterdam, 1984. · Zbl 0705.05057 |
| [6] | 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. · Zbl 0747.05073 |
| [7] | 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. · Zbl 0678.05038 · doi:10.1016/0024-3795(89)90466-7 |
| [8] | F. C. Bussemaker, D. H. Cvetković, and J. J. Seidel, Graphs related to exceptional root systems, Report TH Eindhoven 76-WSK-05, 1976. · Zbl 0338.05116 |
| [9] | 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. · Zbl 0482.05024 |
| [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), no. 1, 305 – 327. · Zbl 0337.05142 · doi:10.1016/0021-8693(76)90162-9 |
| [11] | Chang Li-ch’ien, The uniqueness and nonuniqueness of the triangular association schemes., Sci. Record (N.S.) 3 (1959), 604 – 613. · Zbl 0089.15102 |
| [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. · Zbl 0093.32101 |
| [13] | M. Chein, Recherche des graphes des matrices de Coxeter hyperboliques d’ordre \le 10, Rev. Française Informat. Recherche Opérationnelle 3 (1969), no. Sér. R-3, 3 – 16 (French). · Zbl 0276.20043 |
| [14] | Frank H. Clarke, A graph polynomial and its applications, Discrete Math. 3 (1972), 305 – 313. · Zbl 0244.05111 · doi:10.1016/0012-365X(72)90088-X |
| [15] | H. S. M. Coxeter, Extreme forms, Canadian J. Math. 3 (1951), 391 – 441. · Zbl 0044.04201 |
| [16] | 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. · Zbl 0504.05040 |
| [17] | 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. · Zbl 0824.05046 |
| [18] | Dragoš Cvetković, Michael Doob, and Slobodan Simić, Generalized line graphs, J. Graph Theory 5 (1981), no. 4, 385 – 399. · Zbl 0475.05061 · doi:10.1002/jgt.3190050408 |
| [19] | Michael Doob, An interrelation between line graphs, eigenvalues, and matroids, J. Combinatorial Theory Ser. B. 15 (1973), 40 – 50. · Zbl 0245.05125 |
| [20] | Michael Doob, A surprising property of the least eigenvalue of a graph, Linear Algebra Appl. 46 (1982), 1 – 7. · Zbl 0503.05044 · doi:10.1016/0024-3795(82)90021-0 |
| [21] | Michael Doob and Dragoš Cvetković, On spectral characterizations and embeddings of graphs, Linear Algebra Appl. 27 (1979), 17 – 26. · Zbl 0417.05025 · doi:10.1016/0024-3795(79)90028-4 |
| [22] | Yoshimi Egawa, Characterization of \?(\?,\?) by the parameters, J. Combin. Theory Ser. A 31 (1981), no. 2, 108 – 125. · Zbl 0472.05056 · doi:10.1016/0097-3165(81)90007-8 |
| [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] | Howard Hiller, Geometry of Coxeter groups, Research Notes in Mathematics, vol. 54, Pitman (Advanced Publishing Program), Boston, Mass.-London, 1982. · Zbl 0483.57002 |
| [25] | 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. |
| [26] | A. J. Hoffman, On graphs whose least eigenvalue exceeds -1-\sqrt 2, Linear Algebra and Appl. 16 (1977), no. 2, 153 – 165. · Zbl 0354.05048 |
| [27] | 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), Springer, Berlin, 1972, pp. 165 – 172. Lecture Notes in Math., Vol. 303. · Zbl 0297.15016 |
| [28] | Q. M. Husain, On the totality of the solutions for the symmetrical incomplete block designs: \?=2,\?=5 or 6, Sankhyā 7 (1945), 204 – 208. · Zbl 0060.31407 |
| [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. · Zbl 0494.05044 · doi:10.1016/0024-3795(82)90023-4 |
| [31] | P. W. H. Lemmens and J. J. Seidel, Equiangular lines, J. Algebra 24 (1973), 494 – 512. · Zbl 0255.50005 · doi:10.1016/0021-8693(73)90123-3 |
| [32] | G. A. Miller, H. F. Blichfeldt, and L. E. Dickson, Theory and applications of finite groups, Dover Publications, Inc., New York, 1961. · Zbl 0098.25103 |
| [33] | A. Neumaier, Lattices of simplex type, SIAM J. Algebraic Discrete Methods 4 (1983), no. 2, 145 – 160. · Zbl 0537.51018 · doi:10.1137/0604017 |
| [34] | A. Neumaier, Characterization of a class of distance regular graphs, J. Reine Angew. Math. 357 (1985), 182 – 192. · Zbl 0552.05042 · doi:10.1515/crll.1985.357.182 |
| [35] | 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. · Zbl 0494.05053 |
| [36] | J. J. Seidel, Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3, Linear Algebra and Appl. 1 (1968), 281 – 298. · Zbl 0159.25403 |
| [37] | S. S. Shrikhande, The uniqueness of the \?\(_{2}\) association scheme, Ann. Math. Statist. 30 (1959), 781 – 798. · Zbl 0086.34802 · doi:10.1214/aoms/1177706207 |
| [38] | 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. |
| [39] | D. E. Taylor, Regular 2-graphs, Proc. London Math. Soc. (3) 35 (1977), no. 2, 257 – 274. · Zbl 0362.05065 · doi:10.1112/plms/s3-35.2.257 |
| [40] | Paul Terwilliger, Distance-regular graphs with girth 3 or 4. I, J. Combin. Theory Ser. B 39 (1985), no. 3, 265 – 281. · Zbl 0588.05039 · doi:10.1016/0095-8956(85)90054-1 |
| [41] | Paul Terwilliger, A class of distance-regular graphs that are \?-polynomial, J. Combin. Theory Ser. B 40 (1986), no. 2, 213 – 223. · Zbl 0579.05029 · doi:10.1016/0095-8956(86)90078-X |
| [42] | Paul Terwilliger, Root systems and the Johnson and Hamming graphs, European J. Combin. 8 (1987), no. 1, 73 – 102. · Zbl 0614.05048 · doi:10.1016/S0195-6698(87)80023-9 |
| [43] | Paul Terwilliger, A new feasibility condition for distance-regular graphs, Discrete Math. 61 (1986), no. 2-3, 311 – 315. · Zbl 0606.05045 · doi:10.1016/0012-365X(86)90102-0 |
| [44] | 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. · Zbl 0629.05046 |
| [45] | Ernst Witt, Spiegelungsgruppen und Aufzählung halbeinfacher Liescher Ringe, Abh. Math. Sem. Hansischen Univ. 14 (1941), 289 – 322 (German). · Zbl 0025.30202 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
