Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian

Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian: "

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.

• Content Type Journal Article
• Category Full Length Paper
• DOI 10.1007/s10107-010-0344-z
• Authors
  
  
  • Frank Göring, Technische Universität Chemnitz Fakultät für Mathematik 09107 Chemnitz Germany
  • Christoph Helmberg, Technische Universität Chemnitz Fakultät für Mathematik 09107 Chemnitz Germany
  • Susanna Reiss, Technische Universität Chemnitz Fakultät für Mathematik 09107 Chemnitz Germany
  
  

• Journal Mathematical Programming
• Online ISSN 1436-4646
• Print ISSN 0025-5610

"