Resistance distance and Kirchhoff index in circulant graphs

摘要

The resistance distance r(ij) between vertices i and j of a connected (molecular) graph G is computed as the effective resistance between nodes i and j in the corresponding network constructed from G by replacing each edge of G with a unit resistor. The Kirchhoff index Kf (G) is the sum of resistance distances between all pairs of vertices. In this work, closed-form formulae for Kirchhoff index and resistance distances of circulant graphs are derived in terms of Laplacian spectrum and eigenvectors. Special formulae are also given for four classes of circulant graphs complete graphs, complete graphs minus a perfect matching, cycles, Mobius ladders M-p). In particular, the asymptotic behavior of Kf (Mp) as p -> infinity is obtained, that is, Kf (M-p) grows as (1)/(6)p(3) as p -> infinity. (c) 2006 Wiley Periodicals, Inc.