Hitting Times, Cover Cost, and the Wiener Index of a Tree
From MaRDI portal
Publication:2978178
DOI10.1002/JGT.22029zbMATH Open1359.05113arXiv1302.3212OpenAlexW2141264125MaRDI QIDQ2978178
No author found.
Publication date: 21 April 2017
Published in: Journal of Graph Theory (Search for Journal in Brave)
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 behaviour or random walk on a graph to its eigenvalues in a new perspective.
Full work available at URL: https://arxiv.org/abs/1302.3212
Cites Work
- Unnamed Item
- Random walks and the effective resistance of networks
- Resistance distance and the normalized Laplacian spectrum
- Eigenvalues, diameter, and mean distance in graphs
- Computing the average distance of an interval graph
- Collecting coupons on trees, and the cover time of random walks
- Collisions Among Random Walks on a Graph
- An edge version of the matrix-tree theorem and the wiener index
- Uniqueness of electrical currents in a network of finite total resistance
- Distance in graphs
- Algebraic Potential Theory on Graphs
- Extremal cover times for random walks on trees
- Centers for Random Walks on Trees
- Wiener index of trees: Theory and applications
Related Items (28)
Further results on the expected hitting time, the cover cost and the related invariants of graphs ⋮ Some further results on the maximal hitting times of trees with some given parameters ⋮ On the resistance distance and Kirchhoff index of a linear hexagonal (cylinder) chain ⋮ General multiplicative Zagreb indices of trees ⋮ Extremal hitting times of trees with some given parameters ⋮ Market sentiments and convergence dynamics in decentralized assignment economies ⋮ Random walk hitting times and effective resistance in sparsely connected Erdős‐Rényi random graphs ⋮ Hitting times for random walks on tricyclic graphs ⋮ Two-point resistances in the generalized phenylenes ⋮ On the (reverse) cover cost of trees with some given parameters ⋮ The best mixing time for random walks on trees ⋮ Bicyclic graphs with extremal cover cost ⋮ Kemeny's constant and the Kirchhoff index for the cluster of highly symmetric graphs ⋮ Metric properties of generalized Sierpiński graphs over stars ⋮ Expected hitting times for random walks on quadrilateral graphs and their applications ⋮ Extremal problems on \(k\)-ary trees with respect to the cover cost and reverse cover cost ⋮ Stochastic growth tree networks with an identical fractal dimension: construction and mean hitting time for random walks ⋮ On the weighted reverse cover cost of trees and unicyclic graphs with given diameter ⋮ Expected hitting times for random walks on the diamond hierarchical graphs involving some classical parameters ⋮ On the extremal graphs with respect to the total reciprocal edge-eccentricity ⋮ Extremal cover cost and reverse cover cost of trees with given segment sequence ⋮ The hitting times of random walks on bicyclic graphs ⋮ Chung-Yau Invariants and Graphs with Symmetric Hitting Times ⋮ Expected hitting times for random walks on the \(k\)-triangle graph and their applications ⋮ Unnamed Item ⋮ Wiener index of unicycle graphs with given number of even degree vertices ⋮ The hitting time of random walk on unicyclic graphs ⋮ Dumbbell graphs with extremal (reverse) cover cost
This page was built for publication: Hitting Times, Cover Cost, and the Wiener Index of a Tree
