On the Fiedler vectors of graphs that arise from trees by Schur complementation of the Laplacian

Eric A. Stone*, Alexander R. Griffing

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

Abstract

The utility of Fiedler vectors in interrogating the structure of graphs has generated intense interest and motivated the pursuit of further theoretical results. This paper focuses on how the Fiedler vectors of one graph reveal structure in a second graph that is related to the first. Specifically, we consider a point of articulation r in the graph G whose Laplacian matrix is L and derive a related graph G{r} whose Laplacian is the matrix obtained by taking the Schur complement with respect to r in L. We show how Fiedler vectors of G{r} relate to the structure of G and we provide bounds for the algebraic connectivity of G{r} in terms of the connected components at r in G. In the case where G is a tree with points of articulation r ∈ R, we further consider the graph GR derived from G by taking the Schur complement with respect to R in L. We show that Fiedler vectors of GR valuate the pendent vertices of G in a manner consistent with the structure of the tree.

Original languageEnglish
Pages (from-to)1869-1880
Number of pages12
JournalLinear Algebra and Its Applications
Volume431
Issue number10
DOIs
Publication statusPublished - 15 Oct 2009
Externally publishedYes

Fingerprint

Dive into the research topics of 'On the Fiedler vectors of graphs that arise from trees by Schur complementation of the Laplacian'. Together they form a unique fingerprint.

Cite this