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

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 G R derived from G by taking the Schur complement with respect to R in L . We show that Fiedler vectors of G R valuate the pendent vertices of G in a manner consistent with the structure of the tree.