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