The Laplacian spectrum of graphs

Abstract

In this thesis we investigate the spectrum of the Laplacian matrix of a graph. Although its use dates back to Kirchhoff, most of the major results are much more recent. It is seen to reflect in a very natural way the structure of the graph, particularly those aspects related to connectedness. This can be intuitively understood as a consequence of the relationship between the Laplacian matrix and the boundary of a set of vertices in the graph. We investigate the relationship between the spectrum and the isoperimetric constant, expansion properties, and diameter of the graph. We consider the problem of integral spectra, and see how the structure of the eigenvectors can be used to deduce more information on both the spectrum and the graph, particularly for trees. In closing, we mention some alternatives to and generalisations of the Laplacian.