Optimization Online


Graph Realizations Associated with Minimizing the Maximum Eigenvalue of the Laplacian

Frank Göring(frank.goering***at***mathematik.tu-chemnitz.de)
Christoph Helmberg(helmberg***at***mathematik.tu-chemnitz.de)
Susanna Reiss(susanna.reiss***at***mathematik.tu-chemnitz.de)

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

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Preprint 2009-10, Fakultät für Mathematik, Technische Universität Chemnitz, D-09107 Chemnitz, May 2009

Download: [PDF]

Entry Submitted: 05/25/2009
Entry Accepted: 05/25/2009
Entry Last Modified: 05/25/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society