On a bound on algebraic connectivity: the case of equality
Czechoslovak Mathematical Journal, Tome 48 (1998) no. 1, pp. 65-76
Voir la notice de l'article provenant de la source Czech Digital Mathematics Library
In a recent paper the authors proposed a lower bound on $1 - \lambda _i$, where $\lambda _i$, $ \lambda _i \ne 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.
@article{CMJ_1998__48_1_a5,
author = {Kirkland, Stephen J. and Neumann, Michael and Shader, Bryan L.},
title = {On a bound on algebraic connectivity: the case of equality},
journal = {Czechoslovak Mathematical Journal},
pages = {65--76},
publisher = {mathdoc},
volume = {48},
number = {1},
year = {1998},
mrnumber = {1614076},
zbl = {0931.15013},
language = {en},
url = {http://geodesic.mathdoc.fr/item/CMJ_1998__48_1_a5/}
}
TY - JOUR AU - Kirkland, Stephen J. AU - Neumann, Michael AU - Shader, Bryan L. TI - On a bound on algebraic connectivity: the case of equality JO - Czechoslovak Mathematical Journal PY - 1998 SP - 65 EP - 76 VL - 48 IS - 1 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/CMJ_1998__48_1_a5/ LA - en ID - CMJ_1998__48_1_a5 ER -
%0 Journal Article %A Kirkland, Stephen J. %A Neumann, Michael %A Shader, Bryan L. %T On a bound on algebraic connectivity: the case of equality %J Czechoslovak Mathematical Journal %D 1998 %P 65-76 %V 48 %N 1 %I mathdoc %U http://geodesic.mathdoc.fr/item/CMJ_1998__48_1_a5/ %G en %F CMJ_1998__48_1_a5
Kirkland, Stephen J.; Neumann, Michael; Shader, Bryan L. On a bound on algebraic connectivity: the case of equality. Czechoslovak Mathematical Journal, Tome 48 (1998) no. 1, pp. 65-76. http://geodesic.mathdoc.fr/item/CMJ_1998__48_1_a5/