2020/03/18 by Ciardo, Lorenzo, Dahl, Geir, Kirkland, Steve · 2 citations
#05C12 #05C50 #05C81 #60J10 #94C15 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2003.08286
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.