Navigation

Inhalt Hotkeys
Fakultät für Mathematik
Fakultät für Mathematik
Frank Göring, Christoph Helmberg, Susanna Reiss: On Minimizing the Spectral Width of Graph Laplacians and Associated Graph Realizations

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

Presseartikel

  • MINT gewinnt

    Drei sächsische Hochschulen verfolgen unterschiedliche Konzepte, um Studieninteressenten Mathematik, Informatik, Naturwissenschaften und Technik schmackhaft zu machen …

  • Mathematik ganz alltagsnah

    „Videowoche der Mathematik“ zeigt das Fach von seiner spannenden, menschlichen und alltagstauglichen Seite …

  • Wahlzeit an der Universität

    Wahlvorschläge für Organe und Ämter an der TU Chemnitz können bis zum 23. Oktober 2017 eingereicht werden – Briefwahlanträge sind bis 27. Oktober 2017 zu stellen …