Spectra, Hitting Times and Resistance Distances of q- Subdivision Graphs. (9th December 2019)

• Record Type: Journal Article
• Authors: Zeng, Yibo; Zhang, Zhongzhi
• Is Part Of: Computer journal. Volume 64:Number 1(2021)
• Page Start: 76
• Page End: 92
• Publication Date: 2019-12-09
• Subjects: normalized Laplacian spectrum -- subdivision graph -- random walk -- hitting time -- Kirchhoff index -- effective resistance; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxz141
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: 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.