Paper Info
Title
Hitting times and resistance distances of q-triangulation graphs: Accurate results and applications.
Abstract
Graph operations or products, such as triangulation and Kronecker product have been extensively applied to model complex networks with striking properties observed in real-world complex systems. In this paper, we study hitting times and resistance distances of $q$-triangulation graphs. For a simple connected graph $G$, its $q$-triangulation graph $R_q(G)$ is obtained from $G$ by performing the $q$-triangulation operation on $G$. That is, for every edge $uv$ in $G$, we add $q$ disjoint paths of length $2$, each having $u$ and $v$ as its ends. We first derive the eigenvalues and eigenvectors of normalized adjacency matrix of $R_q(G)$, expressing them in terms of those associated with $G$. Based on these results, we further obtain some interesting quantities about random walks and resistance distances for $R_q(G)$, including two-node hitting time, Kemenyu0027s constant, two-node resistance distance, Kirchhoff index, additive degree-Kirchhoff index, and multiplicative degree-Kirchhoff index. Finally, we provide exact formulas for the aforementioned quantities of iterated $q$-triangulation graphs, using which we provide closed-form expressions for those quantities corresponding to a class of scale-free small-world graphs, which has been applied to mimic complex networks.
Year
Venue
Field
2018
arXiv: Combinatorics
Adjacency matrix,Graph operations,Discrete mathematics,Combinatorics,Disjoint sets,Kronecker product,Random walk,Resistance distance,Hitting time,Connectivity,Mathematics
DocType
Volume
Citations 
Journal
abs/1808.01025
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Yibo Zeng100.68
Zhongzhi Zhang28522.02