标题： 随机游动和树的相遇时间 显示英文标题

标题： Random Walks and the Meeting Time for Trees

摘要： 考虑一棵树$G=(V,E)$上的随机游走。 对于$v,w \in V$，令到达时间$H(v,w)$表示从$v$出发的随机游走到达$w$所需的期望步数，令$\pi_v = \mathrm{deg}(v)/2|E|$表示随机游走的平稳分布。 我们表征了相遇时间$T_{\mathrm{meet}}(G) = \max_{w \in V} \sum_{v \in V} \pi_v H(v,w)$的极端树结构。 对于固定阶数$n$和直径$d$，会合时间由扫帚图最大化。 会合时间由平衡双扫帚图或其微小变体最小化，具体取决于$n$和$d$的相对奇偶性。 显示英文摘要

摘要： Consider a random walk on a tree $G=(V,E)$. For $v,w \in V$, let the hitting time $H(v,w)$ denote the expected number of steps required for the random walk started at $v$ to reach $w$, and let $\pi_v = \mathrm{deg}(v)/2|E|$ denote the stationary distribution for the random walk. We characterize the extremal tree structures for the meeting time $T_{\mathrm{meet}}(G) = \max_{w \in V} \sum_{v \in V} \pi_v H(v,w)$. For fixed order $n$ and diameter $d$, the meeting time is maximized by the broom graph. The meeting time is minimized by the balanced double broom graph, or a slight variant, depending on the relative parities of $n$ and $d$.