Hitting Times,Cover Cost,and the Wiener Index of a Tree

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.