Premium
Broder and Karlin's formula for hitting times and the Kirchhoff Index
Author(s) -
Palacios José Luis,
Renom José M.
Publication year - 2011
Publication title -
international journal of quantum chemistry
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.484
H-Index - 105
eISSN - 1097-461X
pISSN - 0020-7608
DOI - 10.1002/qua.22396
Subject(s) - mathematics , ergodic theory , upper and lower bounds , vertex (graph theory) , combinatorics , markov chain , graph , constant (computer programming) , random walk , discrete mathematics , pure mathematics , mathematical analysis , computer science , programming language , statistics
We give an elementary proof of an extension of Broder and Karlin's formula for the hitting times of an arbitrary ergodic Markov chain. Using this formula in the particular case of random walks on graphs, we give upper and tight lower bounds for the Kirchhoff index of any N ‐ vertex graph in terms of N and its maximal and minimal degrees. We also apply the formula to a closely related index that takes into account the degrees of the vertices between which the effective resistances are computed. We give an upper bound for this alternative index and show that the bound is attained—up to a constant—for the barbell graph. © 2009 Wiley Periodicals, Inc. Int J Quantum Chem, 2011