Further results on the expected hitting time, the cover cost and the related invariants of graphs

2017/07/07 by Jing Huang, Shuchao Li, Huang, Jing +3
Chemistry · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Markov Chains and Monte Carlo Methods #Synthesis and Properties of Aromatic Compounds

paper · pdf · doi:10.48550/arxiv.1707.02002

openalex publication_date 2017/07/07 · openalex created_date 2017/07/14 · openalex updated_date 2026/07/28

Abstract

A close relation between hitting times of the simple random walk on a graph, the Kirchhoff index, resistance-centrality, and related invariants of unicyclic graphs is displayed. Combining with the graph transformations and some other techniques, sharp upper and lower bounds on the cover cost (resp. reverse cover cost) of a vertex in an n-vertex unicyclic graph are determined. All the corresponding extremal graphs are identified, respectively.

Related

• Hitting Times, Cover Cost, and the Wiener Index of a Tree
• A Tractable Variant of Cover Time
• The Cover Time of Random Walks on Graphs
• Cover time of a random graph with a degree sequence II: Allowing vertices of degree two
• Vertex Cover Gets Faster and Harder on Low Degree Graphs