论文标题
关于凯门尼的固定秩和直径的树木的常数
On Kemeny's constant for trees with fixed order and diameter
论文作者
论文摘要
连接图$ G $的Kemeny的常数$κ（G）$是与$ G $相关的随机步行的预期运输时间的量度。在目前的工作中，我们考虑$ g $是一棵树的情况，在这种情况下，我们使用两种不同的技术，就$ n $和直径$ n $和直径$ n $和直径$δ$ $ g $的$κ（g）$提供。下限是作为特定毛毛虫树的凯门尼的常数，因此，它是锋利的。通过归纳可以通过$ g $逐次删除吊坠顶点来找到上限。通过考虑特定的树木家族 - 扫帚明星 - 我们表明上限在渐近上是锋利的。
Kemeny's constant $κ(G)$ of a connected graph $G$ is a measure of the expected transit time for the random walk associated with $G$. In the current work, we consider the case when $G$ is a tree, and, in this setting, we provide lower and upper bounds for $κ(G)$ in terms of the order $n$ and diameter $δ$ of $G$ by using two different techniques. The lower bound is given as Kemeny's constant of a particular caterpillar tree and, as a consequence, it is sharp. The upper bound is found via induction, by repeatedly removing pendent vertices from $G$. By considering a specific family of trees - the broom-stars - we show that the upper bound is asymptotically sharp.
