Spectral Graph Theory and the Inverse Eigenvalue Problem of a Graph

The Inverse Eigenvalue Problem of a Graph is to determine the possible spectra among real symmetric matrices whose pattern of nonzero off-diagonal entries is described by a graph. In the last fifteen years a number of papers on this problem have appeared. Spectral Graph Theory is the study of the spectra of certain matrices defined from a given graph, including the adjacency matrix, the Laplacian matrix and other related matrices. Graph spectra have been studied extensively for more than fifty years. In 1990 Colin de Verdière introduced the first of several graph parameters defined as the maximum multiplicity of eigenvalue 0 among real symmetric matrices described by a graph and satisfying additional conditions. Recent work on Colin de Verdière-type parameters is bringing the two areas closer together. This paper surveys results on the Inverse Eigenvalue Problem of a Graph, Spectral Graph Theory, and Colin de Verdière-type parameters, and examines the connections between these fields.