Name
Title | ||
|---|---|---|
On Minimizing the Spectral Width of Graph Laplacians and Associated Graph Realizations. |
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. For example, the value of a uniform sparsest cut is bounded from below and above by the second smallest and the largest eigenvalue of the weighted Laplacian divided by the number of nodes of the graph. Minimizing the difference between maximum and second smallest eigenvalue over edge weighted Laplacians of a graph reduces the size of this interval. We study this problem of minimizing the spectral width for its own sake with the goal of advancing the understanding of connections between structural properties of the graph and the corresponding eigenvectors and eigenvalues. Building on previous work where these eigenvalues were investigated separately, we show that a corresponding dual problem allows us 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 toward the barycenter along separators, while for the second smallest eigenvalue they fold outward along separators. Furthermore, optimal realizations exist in dimension at most the tree-width of the graph plus one. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1137/110859658 | SIAM JOURNAL ON OPTIMIZATION |
Keywords | DocType | Volume |
spectral graph theory,semidefinite programming,eigenvalue optimization,embedding,tree-width | Journal | 23 |
Issue | ISSN | Citations |
2 | 1052-6234 | 0 |
PageRank | References | Authors |
0.34 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frank Göring | 1 | 53 | 9.00 |
| Christoph Helmberg | 2 | 525 | 63.91 |
| Susanna Reiss | 3 | 6 | 1.63 |