给定直径的树上的随机游动接触时

The Access Time of Random Walks on Trees with Given Diameter

记T(n,d)为n个顶点且直径为d的树的集合.对T∈T(n,d),max_(i∈V)H(π,i)和min_(i∈V)H(π,i)分别表示从平稳分布出发、最终终止于T中某一点的最优终止规则所决定的那些随机游动中所走的平均步数的最大值和最小值.本文通过对树T进行一些图的变换来减小或增大max_(i∈V)H(π,i)与min_(i∈V)H(π,i),从而确定了T(n,d)中分别取到max_(i∈V)H(π,i)上界以及min_(i∈V)H(π,i)下界的极图.此外还确定了直径不大于4的树中分别取到max_(i∈V)H(π,i)下界和min_(i∈V)H(π,i)上界的图.本文的部分结果是对[Graphs Combin.,2013,29(4):757-772]中相应结论的推广.

Let T(n,d)be the set of trees on n vertices with diameter d.For a tree T∈T(n,d),let max_(i∈V)H(π,i)and min_(i∈V)H(π,i)denote the maximum and minimum expected lengths of optimal stopping rules from the stationary distributionπto a vertex of T,respectively.In this paper,we introduce some transformations to decrease or increase max_(i∈V)H(π,i)and min_(i∈V)H(π,i)of T.By using such transformations,we determine the trees maximizing max_(i∈V)H(π,i)and minimizing min_(i∈V)H(π,2)among T(n,d),respectively.Furthermore,we also determine the trees minimizing max_(i∈V)H(π,i)and maximizing min_(i∈V)H(π,i)among T(n,d)when d<4.Parts of our results generalize those previous ones in[Graphs Combin.,2013,29(4):757-772].