ELA, Volume 14, pp. 12-31, January 2005, abstract.

Spectral Graph Theory and the Inverse Eigenvalue 
Problem of a Graph

Leslie Hogben

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 the last 
fifteen years, interest has developed in the study 
of generalized Laplacian matrices of a graph, that is,
real symmetric matrices with negative off-diagonal 
entries in the positions described by the edges of the 
graph (and zero in every other off-diagonal position).

The set of all real symmetric matrices having nonzero 
off-diagonal entries exactly where the graph G has
edges is denoted by S(G). Given a graph G, the problem 
of characterizing the possible spectra of B, such that 
B belongs to S(G), has been referred to as the
"Inverse Eigenvalue Problem of a Graph". In the last 
fifteen years a number of papers on this problem have 
appeared, primarily concerning trees.

The adjacency matrix and Laplacian matrix of G and 
their normalized forms are all in S(G). Recent work on 
generalized Laplacians and Colin de Verdiere matrices 
is bringing the two areas closer together. This paper 
surveys results in Spectral Graph Theory and the 
Inverse Eigenvalue Problem of a Graph, examines the 
connections between these problems, and presents some 
new results on construction of a matrix of minimum 
rank for a given graph having a special form such
as a 0,1-matrix or a generalized Laplacian.