Wissen, was gut ist. Studieren in Chemnitz.
Christoph Helmberg, Susanna Reiss : A note on Fiedler vectors interpreted as graph realizations

Christoph Helmberg, Susanna Reiss : A note on Fiedler vectors interpreted as graph realizations

Author(s):
Christoph Helmberg
Susanna Reiss
Title:
A note on Fiedler vectors interpreted as graph realizations
Electronic source:
application/pdf
Preprint series:
Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 1, 2010
Mathematics Subject Classification:
05C50 [ Graphs and matrices ]
90C22 [ Semidefinite programming ]
90C35 [ Programming involving graphs or networks ]
05C10 [ Topological graph theory, imbedding ]
05C78 [ Graph labelling ]
Abstract:
The second smallest eigenvalue of the Laplace matrix of a graph and its eigenvectors, also known as Fiedler vectors in spectral graph partitioning, carry significant structural information regarding the connectivity of the graph. Using semidefinite programming duality we offer a geometric interpretation of this eigenspace as optimal solution to a graph realization problem. A corresponding interpretation is also given for the eigenspace of the maximum eigenvalue of the Laplacian.
Keywords:
spectral graph theory, semidefinite programming, eigenvalue optimization, embedding, graph partitioning
Language:
English
Publication time:
01/2010