Hitting Times, Cover Cost, and the Wiener Index of a Tree. Issue 3 (29th February 2016)

• Record Type: Journal Article
• Authors: Georgakopoulos, Agelos; Wagner, Stephan
• Is Part Of: Journal of graph theory. Volume 84:Issue 3(2017)
• Page Start: 311
• Page End: 326
• Publication Date: 2016-02-29
• Subjects: random walk -- hitting times -- cover time -- cover cost -- Wiener index -- 05C81; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22029
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: We exhibit a close connection between hitting times of the simple random walk on a graph, the Wiener index, and related graph invariants. In the case of trees, we obtain a simple identity relating hitting times to the Wiener index. It is well known that the vertices of any graph can be put in a linear preorder so that vertices appearing earlier in the preorder are "easier to reach" by a random walk, but "more difficult to get out of." We define various other natural preorders and study their relationships. These preorders coincide when the graph is a tree, but not necessarily otherwise. Our treatise is self‐contained, and puts some known results relating the behavior or random walk on a graph to its eigenvalues in a new perspective.