Resistance distance in graphs and random walks

摘要

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 x 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. (C) 2001 John Wiley & Sons, Inc. [References: 17]