Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian

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 possi...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2012-02, Vol.131 (1-2), p.95-111
Main Authors: Göring, Frank, Helmberg, Christoph, Reiss, Susanna
Format: Article
Language:English
Subjects:
Algebra
Analogies
Applied sciences
Calculus of Variations and Optimal Control
Optimization
Center of gravity
Combinatorics
Combinatorics. Ordered structures
Connectivity
Eigenvalues
Exact sciences and technology
Flows in networks. Combinatorial problems
Full Length Paper
Graph theory
Graphs
Hulls
Hulls (structures)
Laplace transforms
Linear and multilinear algebra, matrix theory
Mathematical analysis
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematical programming
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Operational research and scientific management
Operational research. Management science
Optimization
Origins
Sciences and techniques of general use
Semidefinite programming
Studies
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-010-0344-z