Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2109.09249 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- For a connected graph $G$, the average hitting time $α(G)$ and the Kemeny's constant $κ(G)$ are two similar quantities, both measuring the time for the random walk on $G$ to travel between two randomly chosen vertices. We prove that, among all weighted trees whose edge weights form a fixed multiset, $α$ is maximized by a special type of ``polarized'' paths and is minimized by a unique weighted star graph. We also obtain a similar characterization of the $κ$-maximizing and $κ$-minimizing elements among such a collection of weighted trees. Our proofs are based on the forest formulas for $α$ and $κ$.