Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8900670 | Applied Mathematics and Computation | 2018 | 13 Pages |
Abstract
Given a simple connected graph G, the k-triangle graph of G, written by Tk(G), is obtained from G by adding k new vertices ui1,ui2,â¦,uik for each edge ei=uv in G and then adding in edges uui1,uui2,â¦,uuik and ui1v,ui2v,â¦,uikv. In this paper, the eigenvalues and eigenvectors of the probability transition matrix of random walks on Tk(G) are completely determined. Then the expected hitting times between any two vertices of Tk(G) are given in terms of those of G. Using these results all the relationship on the number of spanning trees (resp. Kemeny's constant, the degree-Kirchhoff index) in Tk(G) compared to those of G is found. As well the resistance distance between any two vertices of Tk(G) is given with respect to those of G.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Chengyong Wang, Ziliang Guo, Shuchao Li,