%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 }