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.