We show that if μj is the j-th largest Laplacian eigenvalue, and dj is the j-th largest degree (1 j n) of a connected graph 蚠 on n vertices, then μj dj − j + 2 (1 j n − 1). This settles a conjecture due to Guo.

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...

We characterize the distance-regular graphs with diameter three by giving an expression for the number of vertices at distance two from each given vertex, in terms of the spectrum of the graph.

A graph G has constant u = u(G) if any two vertices that are not adjacent have u common neighbours. G has constant u and u if G has constant u = u(G), and its complement G has constant u = u(G). If such a graph is regular, then it is strongly regular, otherwise precisely two vertex degrees...

The present article is designed to be a contribution to the chapter `Combinatorial Matrix Theory and Graphs' of the Handbook of Linear Algebra, to be published by CRC Press. The format of the handbook is to give just definitions, theorems, and examples; no proofs. In the five sections given...