Kemeny's constant for nonbacktracking random walks

Abstract

Kemeny’s constant for a connected graph $G$ is the expected time for a random walk to reach a randomly chosen vertex, regardless 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 parameters for several families of graphs and provide closed-form expressions for regular and biregular graphs. For nearly all graphs, the non-backtracking variant yields a smaller Kemeny’s constant.

Publication
Random Structures and Algorithms