ISSN:
1572-9141
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract In a recent paper the authors proposed a lower bound on 1 − λ i , where Λ i ≠ 1, is an eigenvalue of a transition matrix T of an ergodic Markov chain. The bound which involved the group inverse of I − T, was derived from a more general bound, due to Bauer, Deutsch, and Stoer, on the eigenvalues of a stochastic matrix other than its constant row sum. Here we adapt the bound to give a lower bound on the algebraic connectivity of an undirected graph, but principally consider the case of equality in the bound when the graph is a weighted tree. It is shown that the bound is sharp only for certain Type I trees. Our proof involves characterizing the case of equality in an upper estimate for certain inner products due to A. Paz.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1022415527627
