The Kirchhoff Index of Some Combinatorial Networks

Abstract

The Kirchhoff index Kf(G) is the sum of the effective resistance distances between all pairs of vertices in G. The hypercube Qn and the folded hypercube FQn are well known networks due to their perfect properties. The graph G∗, constructed from G, is the line graph of the subdivision graph S(G). In this paper, explicit formulae expressing the Kirchhoff index of (Qn)∗ and (FQn)∗ are found by deducing the characteristic polynomial of the Laplacian matrix of G∗ in terms of that of G.