Combinatorial Perron values of trees and bottleneck matrices

Abstract

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 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. This research was first published in Linear and Multilinear Algebra. © Taylor & Francis.