Interlacing eigenvalues and graphs Original Research Article

We give several old and some new applications of eigenvalue interlacing to matrices associated to graphs. Bounds are obtained for characteristic numbers of graphs, such as the size of a 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. We also deal with inequalities and regularity results concerning the structure of graphs and block designs.