On the Fiedler vectors of graphs that arise from trees by Schur complementation of the Laplacian.
On the Fiedler vectors of graphs that arise from trees by Schur complementation of the Laplacian.
复制标题
关于通过拉普拉斯算子的 Schur 补足从树中产生的图的 Fiedler 向量。
DOI：
10.1016/j.laa.2009.06.024
复制
发表时间：
2009
影响因子：
1.1
通讯作者：
Griffing,AlexanderR
中科院分区：
文献类型：
--
作者：
Stone,EricA;Griffing,AlexanderR
Fiedler向量在询问图的结构中的效用产生了强烈的兴趣，并激发了对进一步理论结果的追求。本文主要研究一个图的Fiedler向量如何在与第一个图相关的第二个图中揭示结构。具体地说，我们考虑图G中的一个铰接点r，其Laplacian矩阵是L，并导出一个相关图G{r}，其Laplacian矩阵是通过在L中取关于r的Schur补而获得的。我们展示了G{r}的Fiedler向量与G的结构的关系，并给出了G{r}的代数连通性的界，即G中r处的连通分支。当G是一棵树，其铰接点r∈R时，我们进一步考虑G通过在L中取关于R的Schur补而导出的图GR.我们表明，Fiedler向量GR valuate的悬挂顶点G的树的结构一致的方式。
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 GRderived from G by taking the Schur complement with respect to R in L. We show that Fiedler vectors of GRvaluate the pendent vertices of G in a manner consistent with the structure of the tree.