Combinatorial Perron values of trees and bottleneck matrices - Andrade, Enide
The algebraic connectivity $a(G)$ of a graph $G$ is an important parameter, defined as the second smallest eigenvalue of the Laplacian matrix of $G$. If $T$ is a tree, $a(T)$ is closely related to the Perron values (spectral radius) of so-called bottleneck matrices of subtrees of $T$. In this setting we introduce a new parameter called the {\em combinatorial Perron value} $ρ_c$. This value is a lower bound on the Perron value of such subtrees; typically $ρ_c$ is a good approximation to $ρ$. We compute exact values of $ρ_c$ for certain special subtrees. Moreover, some results concerning $ρ_c$ when the tree is modified are established, and it is shown that, among trees with given distance vector (from the root), $ρ_c$ is maximized for caterpillars.