首页|The access time of random walks on trees with given partition
The access time of random walks on trees with given partition
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
Denote by T(s ,t) the set of trees, whose vertex set can be partitioned into two independent sets of sizes s and t respectively. Given a tree T with stationary distribution pi and a vertex v is an element of T , the access time HT (tau , v ) is the expected length of optimal stopping rules from pi to v . In this paper, we get a sharp upper bound for max(v is an element of T) HT (pi, v ) and a sharp lower bound for min(v is an element of T)H(T)(pi ,v) among T(s ,t), respectively. The corresponding extremal graphs are also obtained. As a byproduct, it is proved that the path Pn maximizes max(v is an element of T) H-T ((pi) over bar, v ) and the star K-1,K-n-1 minimizes minvET HT ((pi) over bar, v ) among all trees on n vertices. (C) 2022 Elsevier Inc. All rights reserved.
TreeRandom walkStopping ruleEXPECTED HITTING TIMES
NSTL
Elsevier
