Premium
Resistance distance in graphs and random walks
Author(s) -
Palacios José Luis
Publication year - 2000
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/1097-461x(2001)81:1<29::aid-qua6>3.0.co;2-y
Subject(s) - random walk , statistical physics , mathematics , combinatorics , physics , statistics
We study the resistance distance on connected undirected graphs, linking this concept to the fruitful area of random walks on graphs. We provide two short proofs of a general lower bound for the resistance, or Kirchhoff index, of graphs on N vertices, as well as an upper bound and a general formula to compute it exactly, whose complexity is that of inverting an N × N matrix. We argue that the formulas for the resistance in the case of the Platonic solids can be generalized to all distance‐transitive graphs. © 2001 John Wiley & Sons, Inc. Int J Quant Chem 81: 29–33, 2001