On a bound on algebraic connectivity: The case of equality

被引:9
作者
Kirkland, SJ
Neumann, M
Shader, BL
机构
[1] Univ Regina, Dept Math & Stat, Regina, SK S4S 0A2, Canada
[2] Univ Connecticut, Dept Math, Storrs, CT 06269 USA
[3] Univ Wyoming, Dept Math, Laramie, WY 82071 USA
基金
加拿大自然科学与工程研究理事会; 美国国家科学基金会;
关键词
Differential Equation; Mathematical Modeling; Markov Chain; Ordinary Differential Equation; Industrial Mathematic;
D O I
10.1023/A:1022415527627
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In a recent paper the authors proposed a lower bound on 1 - lambda(i), where lambda(i), lambda(i) not equal 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 Steer, 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. Pat.
引用
收藏
页码:65 / 76
页数:12
相关论文
共 13 条
[1]  
Bauer F.L., 1969, LINEAR ALGEBRA APPL, V2, P275
[2]  
BENISRAEL A, 1973, GEN INVERSES THEORY
[3]  
Berman A., 1994, CLASSICS APPL MATH, DOI [DOI 10.1137/1.9781611971262, 10.1016/C2013-0-10361-3]
[4]  
Campbell S.L., 1991, Generalized Inverses of Linear Transformations
[5]   INCLUSION DOMAINS FOR EIGENVALUES OF STOCHASTIC MATRICES [J].
DEUTSCH, E ;
ZENGER, C .
NUMERISCHE MATHEMATIK, 1971, 18 (02) :182-&
[6]  
FIEDLER M, 1975, CZECH MATH J, V25, P619
[7]  
KIKLAND SJ, IN PRESS LIN ALG APP
[8]  
Kirkland S., 1996, Linear Multilinear Algebra, V40, P311, DOI [10.1080/03081089608818448, DOI 10.1080/03081089608818448]
[9]   Bounds on the subdominant eigenvalue involving group inverses with applications to graphs [J].
Kirkland, SJ ;
Neumann, M ;
Shader, BL .
CZECHOSLOVAK MATHEMATICAL JOURNAL, 1998, 48 (01) :1-20
[10]  
KIRKLAND SJ, IN PRESS SIAM J MATR