2013/02/13 by Agelos Georgakopoulos, Stephan Wagner, Georgakopoulos, Agelos +1 · 1 citation
Mathematics · #05C35 #05C81 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C35 #msc:05C81
paper · pdf · doi:10.48550/arxiv.1302.3212
To appear in JGT
arxiv created 2015/12/14 · arxiv updated 2015/12/15
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 behaviour or random walk on a graph to its eigenvalues in a new perspective.