

























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 $κ$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。