摘要
记Г(n,d)为n个顶点且直径为d的树的集合.对T ∈ Г(n,d),maxi∈V H(π,i)和mini∈V H(π,i)分别表示从平稳分布出发、最终终止于T中某一点的最优终止规则所决定的那些随机游动中所走的平均步数的最大值和最小值.本文通过对树T进行一些图的变换来减小或增大maxi∈V H(π,i)与mini∈V H(π,i),从而确定了 Г(n,d)中分别取到maxi∈V H(π,i)上界以及mini∈V H(π,i)下界的极图.此外还确定了直径不大于4的树中分别取到maxi∈V H(π,i)下界和 mini∈V H(π,i)上界的图.本文的部分结果是对[Graphs Combin.,2013,29(4):757-772]中相应结论的推广.
Abstract
Let Г(n,d)be the set of trees on n vertices with diameter d.For a tree T ∈ Г(n,d),let maxi∈V H(π,i)and mini∈V H(π,i)denote the maximum and minimum expect-ed lengths of optimal stopping rules from the stationary distribution π to a vertex of T,respec-tively.In this paper,we introduce some transformations to decrease or increase maxi∈V H(π,i)and mini∈V H(π,i)of T.By using such transformations,we determine the trees maximiz-ing maxi∈V H(π,i)and minimizing mini∈V H(π,i)among Г(n,d),respectively.Furthermore,we also determine the trees minimizing maxi∈V H(π,i)and maximizing mini∈V H(π,i)amongГ(n,d)when d≤4.Parts of our results generalize those previous ones in[Graphs Combin.,2013,29(4):757-772].
基金项目
NSFC(12071484)
NSFC(11871479)
Hunan Provincial Natural Science Foundation(2018JJ2479)
Hunan Provincial Natural Science Foundation(2020JJ4675)
Mathematics and Interdisciplinary Sciences Project of CSU()
NETL
NSTL
维普
万方数据