Resistance Distance And Kirchhoff Index In Graphs

The resistance distance r_ij between vertices i and j of a connected 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 an unit resistor. The Kirchhoff index Kf(G) is the sum of resistance distances between all pairs of vertices. In this work, first of all, formulae for Kirchhoff index and resistance distances of circulant graphs are derived in terms of Laplacian spectrum and eigenvectors. Simple 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 Kirchhoff index of Mobius ladders M_p is obtained, that is, Kf(M_p) grows as (1/6)p³ as p → ∞. In the following, formulae are given for Kirchhoff index of strongly regular graphs, P_m × P_n and P₂ × P_n. The asymptotic behavior of Kirchhoff index of P₂ × P_n is also obtained, namely, K f(P₂ × P_n) grows as (n³)/3 as n → ∞. Finally, bounds for Kirchhoff index of bipartite graphs as well as the sufficient and necessary conditions when the bounds are sharp are obtained.