SPECTRAL GRAPH THEORY AND THE INVERSE EIGENVALUE PROBLEM OF A GRAPH

By Leslie Hogben. 2005

103 citations recorded by the source corpus.

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 ∈S (G), has been referred to as the Inverse Eigenvalue Problem of a Graph .I n 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.

Subfields: Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/84ba27f5ed15a9751aaac63d0d5068034351da0a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

Citations in the corpus

A q-analogue of the distance matrix of a tree (2006, background): “L = diag(d)+A, the signless Laplacian matrix of a tree (see [7]), whenever q = −1.”
The minimum rank of symmetric matrices described by a graph: A survey☆ (2007, unknown): “(For a discussion of connections between IEPG and spectral graph theory, see [30].)”
Minimum number of distinct eigenvalues of graphs (2013, background): “For example, the inverse eigenvalue problem for graphs (see [13]) continues to receive considerable and deserved attention, as it remains one of the most interesting unresolved issues in combinatorial matrix theory.”