# On a bound on algebraic connectivity: the case of equality

Stephen J. Kirkland; Neumann, Michael; Bryan L. Shader

Czechoslovak Mathematical Journal (1998)

- Volume: 48, Issue: 1, page 65-76
- ISSN: 0011-4642

## Access Full Article

top## Abstract

top## How to cite

topKirkland, Stephen J., Neumann, Michael, and Shader, Bryan L.. "On a bound on algebraic connectivity: the case of equality." Czechoslovak Mathematical Journal 48.1 (1998): 65-76. <http://eudml.org/doc/30402>.

@article{Kirkland1998,

abstract = {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.},

author = {Kirkland, Stephen J., Neumann, Michael, Shader, Bryan L.},

journal = {Czechoslovak Mathematical Journal},

keywords = {eigenvalues; algebraic connectivity; undirected graphs; lower bound; transition matrix; ergodic Markov chain; group inverse; stochastic matrix},

language = {eng},

number = {1},

pages = {65-76},

publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},

title = {On a bound on algebraic connectivity: the case of equality},

url = {http://eudml.org/doc/30402},

volume = {48},

year = {1998},

}

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

PB - Institute of Mathematics, Academy of Sciences of the Czech Republic

VL - 48

IS - 1

SP - 65

EP - 76

AB - 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.

LA - eng

KW - eigenvalues; algebraic connectivity; undirected graphs; lower bound; transition matrix; ergodic Markov chain; group inverse; stochastic matrix

UR - http://eudml.org/doc/30402

ER -

## References

top- 10.1016/0024-3795(69)90031-7, Lin. Alg. Appl. 2 (1969), 275–301. (1969) MR0245587DOI10.1016/0024-3795(69)90031-7
- Generalized Inverses: Theory and Applications, Academic Press, New-York, 1973. (1973)
- Nonnegative Matrices in the Mathematical Sciences, SIAM Publications, Philadelphia, 1994. (1994) MR1298430
- Generalized Inverses of Linear Transformations, Dover Publications, New York, 1991. (1991) MR1105324
- 10.1007/BF01436327, Numer. Math. 18 (1971), 182–192. (1971) MR0301908DOI10.1007/BF01436327
- Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973), 298–305. (1973) Zbl0265.05119MR0318007
- A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory, Czechoslovak Math. J. 25 (1975), 619–633. (1975) MR0387321
- 10.1023/A:1022455208972, Czechoslovak Math. J. 48(123) (1998), 1–20. (1998) MR1614056DOI10.1023/A:1022455208972
- Distances in weighted trees via group inverses of Laplacian matrices, SIAM J. Matrix Anal. Appl (to appear). (to appear) MR1471996
- 10.1080/03081089608818448, Lin. Multilin. Alg. 40 (1996), 311–325. (1996) MR1384650DOI10.1080/03081089608818448
- Applications of Paz’s inequality to perturbation bounds ffor Markov chains, Lin. Alg. Appl (to appear). (to appear)
- 10.1080/03081088708817827, Lin. Multilin. Alg., 22 (1987), 115–131. (1987) Zbl0636.05021MR0936566DOI10.1080/03081088708817827
- Introduction to Probabilistic Automata, Academic Press, New-York, 1971. (1971) Zbl0234.94055MR0289222
- Non-negative Matrices and Markov Chains. Second Edition, Springer Verlag, New-York, 1981, pp. . (1981) MR2209438

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.