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.
%0 Journal Article
%1 georgakopoulos2016hitting
%A Georgakopoulos, Agelos
%A Wagner, Stephan
%D 2016
%J Journal of Graph Theory
%K hitting_times random_walks_on_graphs resistance_distance trees
%P n/a--n/a
%R 10.1002/jgt.22029
%T Hitting Times, Cover Cost, and the Wiener Index of a Tree
%U http://dx.doi.org/10.1002/jgt.22029
%X 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.
@article{georgakopoulos2016hitting,
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.},
added-at = {2016-03-15T23:28:45.000+0100},
author = {Georgakopoulos, Agelos and Wagner, Stephan},
biburl = {https://www.bibsonomy.org/bibtex/20e0b2a743feaee42e3bed1723abf488b/peter.ralph},
doi = {10.1002/jgt.22029},
interhash = {c85d633f28e846ae2a03d98d92e45b68},
intrahash = {0e0b2a743feaee42e3bed1723abf488b},
issn = {1097-0118},
journal = {Journal of Graph Theory},
keywords = {hitting_times random_walks_on_graphs resistance_distance trees},
pages = {n/a--n/a},
timestamp = {2016-03-15T23:31:56.000+0100},
title = {Hitting Times, Cover Cost, and the {Wiener} Index of a Tree},
url = {http://dx.doi.org/10.1002/jgt.22029},
year = 2016
}