Title: Kemeny's constant for an undirected graph: how much can adding one edge change things?
Abstract: Given a connected graph G, we consider the corresponding random walk, described as follows. Our random walker moves from one vertex to another in discrete time; when the walker is on vertex v at time t, one of the neighbours of v, say v', is chosen at random, and the walker moves to vertex v' at time t+1. The expected time it takes for the random walker to move from a randomly chosen initial vertex to a randomly chosen destination vertex is known as Kemeny's constant, and it can be thought of as measuring the random walker's ease of movement through the graph.
What happens to Kemeny's constant when a new edge is added to G? It turns out that depending on the structure of the graph and the placement of the new edge, Kemeny's constant might increase, or decrease, or stay the same. In this talk, we take a step towards quantifying this behaviour. For each natural number n, we consider the family of trees on n vertices. We identify the tree in that family, as well as the new edge to be added, so that the increase in Kemeny's constant is maximized. We also solve the corresponding problem for maximizing the decrease in Kemeny's constant. The techniques rely on a detailed analysis of distance matrices for trees.