Kirchhoff Index Of 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 of two classes of chordal graphs are derived in terms of Laplacian spectrum. In the following, for a n-vertex p-partite graph G = G(N₁,N₂,..., N_p) (|N_i| =n_i, i = 1,2, ... ,p ; n₁≤n₂≤...≤n_p) we obtain sharp upper and lower bounds for its Kirchhoff index: if 2n_p - n≤1, the upper bound realizes if and only if G is path P_n, otherwise, the upper bound realizes if and only if G is isomorphic to tree T'(n₁, n₂, ... , n_p-1; n_p), and the lower bound holds if and only if G is complete p-partite graph. Furthermore, we obtain that Turan graph has minimal Kirchhoff index among all n-vertex p-partite graphs. Finally, we find that C_n(1, 2) has maximal Kirchhoff index among all n-vertex 4-regular circulant graphs C_n(1, z) with step length 1 and z (2≤z≤[n/2] - 1). By calculation and verification, we obtain the result holds for 7≤n≤30000.