## Interlacing eigenvalues and graphs.(English)Zbl 0831.05044

A survey paper to various kinds of applications of eigenvalue interlacing to matrices associated with graphs. Bounds are obtained for characteristic numbers of graphs, such as the size of maximal (co)clique, the chromatic number, the diameter, and the bandwidth, in terms of the eigenvalues of the standard adjacency matrix or the Laplacian matrix. The paper also deals with inequalities and regularity results concerning the structure of graphs and block designs.

### MSC:

 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 05B05 Combinatorial aspects of block designs
Full Text:

### References:

 [1] Beker, H.J.; Haemers, W.H., 2-designs with an intersection number k - n, J. combin. theory ser. A, 28, 64-81, (1980) · Zbl 0425.05009 [2] Brouwer, A.E., Toughness and spectrum of a graph, Linear algebra appl., 226-228, 267-271, (1995) · Zbl 0833.05048 [3] Brouwer, A.E.; Cohen, A.M.; Neumaier, A., Distance-regular graphs, (1989), Springer-Verlag Berlin · Zbl 0747.05073 [4] Brouwer, A.E.; Haemers, W.H., The gewirtz graph—an exercise in the theory of graph spectra, European J. combin., 14, 397-407, (1993) · Zbl 0794.05076 [5] Brouwer, A.E.; Mesner, D.M., The connectivity of strongly regular graphs, European J. combin., 6, 215-216, (1985) · Zbl 0607.05045 [6] Courant, R.; Hilbert, D., Methoden der mathematischen physik, (1924), Springer-Verlag Berlin · JFM 63.0449.05 [7] Cvetković, D.M., Graphs and their spectra, Publ. elektrotehn. fak. ser. mat. fiz., 354-356, 1-50, (1971) · Zbl 0238.05102 [8] Cvetković, D.M.; Doob, M.; Sachs, H., Spectra of graphs—theory and applications, (1979), V.E.B. Deutscher Verlag der Wissenschaften Berlin [9] van Dam, E.R.; Haemers, W.H., Eigenvalues and the diameter of graphs, (), also Linear Multilinear Algebra, to appear · Zbl 1118.05066 [10] Delorme, C.; Solé, P., Diameter, covering index, covering radius and eigenvalues, European J. combin., 12, 95-108, (1991) · Zbl 0737.05067 [11] Delsarte, P.; Goethals, J.M.; Seidel, J.J., Spherical codes and designs, (), 6, 68-93, (1977), also in · Zbl 0376.05015 [12] Ghinelli, D.; Löwe, S., Generalized quadrangles with a regular point and association schemes, Linear algebra appl., 226-228, 87-104, (1995) · Zbl 0832.51001 [13] Godsil, C.D., Algebraic combinatorics, (1993), Chapman and Hall New York · Zbl 0814.05075 [14] Haemers, W.H., Eigenvalue techniques in design and graph theory, () · Zbl 0429.05013 [15] Haemers, W.H., Eigenvalue methods, (), 15-38 [16] Haemers, W.H., Distance-regularity and the spectrum of graphs, (), also Linear Algebra Appl., to appear · Zbl 0745.51003 [17] Haemers, W.H.; Shrikhande, M.S., Some remarks on subdesigns of symmetric designs, J. statist. plann. inf., 3, 361-366, (1979) · Zbl 0445.05022 [18] Helmberg, C.; Mohar, B.; Poljak, S.; Rendl, F., A spectral approach to bandwidth and separator problems in graphs, (), 183-194 · Zbl 0920.05061 [19] van den Heuvel, J., Hamilton cycles and eigenvalues of graphs, Linear algebra appl., 226-228, (1995) · Zbl 0846.05059 [20] Hoffman, A.J., On eigenvalues and colourings of graphs, (), 79-91 [21] Hughes, D.R.; Piper, F.C., Design theory, (1985), Cambridge U.P · Zbl 0561.05009 [22] Jungnickel, D., On subdesigns of symmetric designs, Math. Z., 181, 383-393, (1982) · Zbl 0496.05008 [23] Lander, E.S., Symmetric designs: an algebraic approach, () · Zbl 0502.05010 [24] Lovász, L., On the Shannon capacity of a graph, IEEE trans. inform. theory, IT-25, 1-7, (1979) · Zbl 0395.94021 [25] Lovász, L., Combinatorial problems and exercises, (1979), North-Holland Amsterdam · Zbl 0439.05001 [26] Majumdar, K.N., On some theorems in combinatorics relating to incomplete block designs, Ann. math. statist., 24, 379-389, (1953) · Zbl 0051.10802 [27] Manolopoulos, D.E.; Woodall, D.R.; Fowler, P.W., Electronic stability of fullerenes: eigenvalue theorems for leapfrog carbon clusters, J. chem. soc. Faraday trans., 88, 2427-2435, (1992) [28] Mohar, B., A domain monotonicity theorem for graphs and Hamiltonicity, Discrete appl. math., 36, 169-177, (1992) · Zbl 0765.05071 [29] Payne, S.E., An inequality for generalized quadrangles, (), 147-152 · Zbl 0357.05027 [30] Payne, S.E.; Thas, J.A., Finite generalized quadrangles, () · Zbl 0551.05027 [31] Peeters, M.J.P., Uniqueness of strongly regular graphs having minimal p-rank, Linear algebra appl., 226-228, 9-31, (1995) · Zbl 0831.05066 [32] Rivlin, T.J., Chebyshev polynomials, (1990), Wiley New York · Zbl 0871.41022 [33] Seidel, J.J., Strongly regular graphs, (), 157-180 · 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.