Back to Search
Start Over
Hitting Times, Cover Cost, and the Wiener Index of a Tree.
- Source :
-
Journal of Graph Theory . Mar2017, Vol. 84 Issue 3, p311-326. 16p. - Publication Year :
- 2017
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *TREE graphs
*GRAPH theory
*IDENTITIES (Mathematics)
*RANDOM walks
*EIGENVALUES
Subjects
Details
- Language :
- English
- ISSN :
- 03649024
- Volume :
- 84
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Journal of Graph Theory
- Publication Type :
- Academic Journal
- Accession number :
- 120747630
- Full Text :
- https://doi.org/10.1002/jgt.22029