Frank Göring, Christoph Helmberg, Susanna Reiss: On Minimizing the Spectral Width of Graph Laplacians and Associated Graph Realizations

Author(s):

Frank Göring
Christoph Helmberg
Susanna Reiss

Title:

On Minimizing the Spectral Width of Graph Laplacians and Associated Graph Realizations

Electronic source:

application/pdf

Preprint series:

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 04, 2011

Mathematics Subject Classification:

05C50	[Graphs and matrices]
90C22	[Semidefinite programming]
90C35	[Programming involving graphs or networks]
05C10	[Topological graph theory, imbedding]

05C78[Graph labelling]

Abstract:

Extremal eigenvalues and eigenvectors of the Laplace matrix of a graph form the core of many bounds on graph parameters and graph optimization problems. In order to advance the understanding of connections between structural properties of the graph and these eigenvectors and eigenvalues we study the problem minimizing the difference between maximum and second smallest eigenvalue over edge weighted Laplacians of a graph. Building on previous work where these eigenvalues were investigated separately, we show that a corresponding dual problem allows to view eigenvectors to optimized eigenvalues as graph realizations in Euclidean space, whose structure is tightly linked to the separator structure of the graph. In particular, optimal realizations corresponding to the maximum eigenvalue fold towards the barycenter along separators while for the second smallest eigenvalue they fold outwards along separators. Furthermore optimal realizations exist in dimension at most the tree-width of the graph plus one.

Keywords:

spectral graph theory, semidefinite programming, eigenvalue optimization, embedding, tree width

Language:

English

Publication time:

02/2011