Expected hitting times for random walks on the k-triangle graph and their applications

Chengyong Wang, Ziliang Guo and Shuchao Li

Applied Mathematics and Computation, 2018, vol. 338, issue C, 698-710

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.

Keywords: Hitting time; k-triangle graph; Kemeny’s constant; Degree-Kirchhoff index; Spanning tree (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300318305459
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:338:y:2018:i:c:p:698-710

DOI: 10.1016/j.amc.2018.06.056

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().