Bounds for the Kirchhoff index of regular graphs via the spectra of their random walks

Using probabilistic tools, we give tight upper and lower bounds for the Kirchhoff index of any d‐regular N‐vertex graph in terms of d, N, and the spectral gap of the transition probability matrix associated to the random walk on the graph. We then use bounds of the spectral gap of more specialized g...

Full description

Saved in:
Bibliographic Details
Published in:International journal of quantum chemistry 2010-08, Vol.110 (9), p.1637-1641
Main Authors: Palacios, José Luis, Renom, José Miguel
Format: Article
Language:English
Subjects:
fundamental matrix
hitting times
Kemeny's constant
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Using probabilistic tools, we give tight upper and lower bounds for the Kirchhoff index of any d‐regular N‐vertex graph in terms of d, N, and the spectral gap of the transition probability matrix associated to the random walk on the graph. We then use bounds of the spectral gap of more specialized graphs, available in the literature, in order to obtain upper bounds for the Kirchhoff index of these specialized graphs. As a byproduct, we obtain a closed‐form formula for the Kirchhoff index of the d‐dimensional cube in terms of the first inverse moment of a positive binomial variable. © 2009 Wiley Periodicals, Inc. Int J Quantum Chem, 2010
ISSN:0020-7608
1097-461X
DOI:10.1002/qua.22323