On the Fiedler vectors of graphs that arise from trees by Schur complementation of the Laplacian
✍ Scribed by Eric A. Stone; Alexander R. Griffing
- Publisher
- Elsevier Science
- Year
- 2009
- Tongue
- English
- Weight
- 225 KB
- Volume
- 431
- Category
- Article
- ISSN
- 0024-3795
No coin nor oath required. For personal study only.
✦ Synopsis
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 in the graph whose Laplacian matrix is and derive a related graph whose Laplacian is the matrix obtained by taking the Schur complement with respect to in . We show how Fiedler vectors of relate to the structure of and we provide bounds for the algebraic connectivity of in terms of the connected components at in . In the case where is a tree with points of articulation ∈ , we further consider the graph derived from by taking the Schur complement with respect to in . We show that Fiedler vectors of valuate the pendent vertices of in a manner consistent with the structure of the tree.