Spectra, Hitting Times and Resistance Distances of q- Subdivision Graphs

摘要

Subdivision, triangulation, Kronecker product, corona product and many other graph operations or products play an important role in complex networks. In this paper, we study the properties of q-subdivision graphs, which have been applied to model complex networks. For a simple connected graph G, its q-subdivision graph S_q(G) is obtained from G through replacing every edge uv in G by q disjoint paths of length 2, with each path having u and v as its ends. We derive explicit formulas for many quantities of S_q(G) in terms of those corresponding to G, including the eigenvalues and eigenvectors of normalized adjacency matrix, two-node hitting time, Kemeny constant, two-node resistance distance, Kirchhoff index, additive degree-Kirchhoff index and multiplicative degree-Kirchhoff index. We also study the properties of the iterated q-subdivision graphs, based on which we obtain the closed-form expressions for a family of hierarchical lattices, which has been used to describe scale-free fractal networks.