Name
Abstract | ||
|---|---|---|
Eigenvectors to the second smallest eigenvalue of the Laplace matrix of a graph, also known as Fiedler vectors, are the basic ingredient in spectral graph partitioning heuristics. Maximizing this second smallest eigenvalue over all nonnegative edge weightings with bounded total weight yields the absolute algebraic connectivity introduced by Fiedler, who proved tight connections of this value to the connectivity of the graph. Our objective is to gain a better understanding of the connections between separators and the eigenspace of this eigenvalue by studying the dual semidefinite optimization problem to the absolute algebraic connectivity. By exploiting optimality conditions we show that this problem is equivalent to finding an embedding of the $n$ nodes of the graph in $n$-space so that their barycenter is the origin, the distance between adjacent nodes is bounded by one, and the nodes are spread as much as possible (the sum of the squared norms is maximized). For connected graphs we prove that, for any separator in the graph, at least one of the two separated node sets is embedded in the shadow (with the origin being the light source) of the convex hull of the separator. Furthermore, we show that there always exists an optimal embedding whose dimension is bounded by the tree width of the graph plus one. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1137/050639430 | SIAM Journal on Optimization |
Keywords | Field | DocType |
laplace matrix,graph plus one. keywords: spectral graph theory,absolute algebraic connectivity,fiedler vector,05c10,semidefinite programming,smallest eigenvalue,adjacent node,eigenvalue optimiza- tion,90c22,05c78,spectral graph,dual semidefinite optimization problem,optimal embedding,tree-width msc 2000: 05c50,graph partitioning,connected graph,90c35,embedding,bounded total weight yield,spectral graph theory,tree width,algebraic connectivity,eigenvalues,convex hull | Discrete mathematics,Combinatorics,Mathematical optimization,Graph energy,Line graph,Algebraic connectivity,Null graph,Connectivity,Voltage graph,Mathematics,Planar graph,Complement graph | Journal |
Volume | Issue | ISSN |
19 | 1 | 1052-6234 |
Citations | PageRank | References |
16 | 2.43 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frank Göring | 1 | 53 | 9.00 |
| Christoph Helmberg | 2 | 525 | 63.91 |
| Markus Wappler | 3 | 19 | 2.84 |