Extreme Values of the Fiedler Vector on Trees

Abstract

Let $G$ be a connected tree on $n$ vertices and let $L=D-A$ denote the Laplacian matrix on $G$. The second-smallest eigenvalue ${\lambda }_2(G)>0$, also known as the algebraic connectivity, as well as the associated eigenvector ${\varphi }_2$ have been of substantial interest. We investigate the question of when the maxima and minima of ${\varphi }_2$ are assumed at the endpoints of the longest path in $G$. Our results also apply to more general graphs that `behave globally' like a tree but can exhibit more complicated local structure. The crucial new ingredient is a reproducing formula for the eigenvector ${\varphi }_k$.

References in corpus (2)

• On the Diffusion Geometry of Graph Laplacians and Applications
• Fiedler Vectors and Elongation of Graphs: A Threshold Phenomenon on a Particular Class of Trees