The Laplacian spectrum of graphs
Loading...
Files
Date
2001-07-01T00:00:00Z
Authors
Newman, Michael William
Journal Title
Journal ISSN
Volume Title
Publisher
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.