ABSTRACT
In Chapter 3, we learned that one motivation for studying Laplacian matrices is that their spectra can give us a great deal of information about the structure of the graph. In this chapter, we investigate the overall spectra of Laplacian matrices. We do this by first investigating the effects on the spectra when we perform certain operations on graphs. We then continue our study more deeply by finding upper bounds on the largest eigenvalue of the Laplacian matrix, hence bounding the set of all eigenvalues of the Laplacian matrix. Once we do that, we are better able to study how the eigenvalues of the Laplacian matrix are distributed. Since 1 is often an eigenvalue, we investigate the properties of graphs that lead to 1 being an eigenvalue of the Laplacian matrix. We then deepen our investigation to see the distribution of eigenvalues less than 1 and eigenvalues greater than 1. By investigating the distribution of the eigenvalues and having the knowledge of an upperbound on the set of all eigenvalues of the Laplacian, we then prove the Grone-Merris Conjecture which gives upper bounds on each eigenvalue individually. This leads us to the study of maximal (threshold) graphs which are graphs in which the Grone-Merris Conjecture is sharp for each eigenvalue. Since the bounds obtained from the GroneMerris Conjecture are integers, it becomes natural to investigate graphs which are Laplacian integral, i.e., graphs whose Laplacian eigenvalues are all integers.
