Spectral Graph Theory and the Inverse Eigenvalue Problem of a Graph

Abstract

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`ere introduced the first of several graph parameters defined as the maximum multiplicity of eigenvalue among real symmetric matrices described by a graph and satisfying additional conditions. Recent work on Colin de Verdi`ere-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`ere-type parameters, and examines the connections between these fields.