Navigation

Inhalt Hotkeys
Fakultät für Mathematik
Fakultät für Mathematik
Göring, Frank; Helmberg, Christoph; Reiss, Susanna : Graph Realizations Associated with Minimizing the Maximum Eigenvalue of the Laplacian

Göring, Frank ; Helmberg, Christoph ; Reiss, Susanna : Graph Realizations Associated with Minimizing the Maximum Eigenvalue of the Laplacian


Author(s):
Göring, Frank
Helmberg, Christoph
Reiss, Susanna
Title:
Graph Realizations Associated with Minimizing the Maximum Eigenvalue of the Laplacian
Electronic source:
application/pdf
Preprint series:
Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 10, 2009
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:
In analogy to the absolute algebraic connectivity of Fiedler, we study the problem of minimizing the maximum eigenvalue of the Laplacian of a graph by redistributing the edge weights. Via semidefinite duality this leads to a graph realization problem in which nodes should be placed as close as possible to the origin while adjacent nodes must keep a distance of at least one. We prove three main results for a slightly generalized form of this embedding problem. First, given a set of vertices partitioning the graph into several or just one part, the barycenter of each part is embedded on the same side of the affine hull of the set as the origin. Second, there is an optimal realization of dimension at most the tree-width of the graph plus one and this bound is best possible in general. Finally, bipartite graphs possess a one dimensional optimal embedding.
Keywords:
spectral graph theory, semidefinite programming, eigenvalue optimization, embedding, graph partitioning, tree-width
Language:
English
Publication time:
5 / 2009

Presseartikel

  • Mehr Mathe dank Diplom

    TU Chemnitz bietet ab dem kommendem Wintersemester den modularisierten Diplomstudiengang Mathematik an …

  • 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 …