2022/03/22 by Breen, Jane, Faught, Nolan, Glover, Cory +3 · 1 citation
#05C50 #05C81 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2203.12049
Kemeny's constant for a connected graph G is the expected time for a random walk to reach a randomly-chosen vertex u, regardless of the choice of the initial vertex. We extend the definition of Kemeny's constant to non-backtracking random walks and compare it to Kemeny's constant for simple random walks. We explore the relationship between these two parameters for several families of graphs and provide closed-form expressions for regular and biregular graphs. In nearly all cases, the non-backtracking variant yields the smaller Kemeny's constant.