Complete multipartite graphs and Braess edges

Abstract

Given an irreducible stochastic matrix T, Kemeny's constant k(T) measures the expected number of steps from any initial state to a randomly chosen final state, and is thus regarded as an indicator of the overall transit efficiency of the corresponding Markov chain. For a random walk on a connected graph with twin vertices, we present a formula for the change in Kemeny's constant after the insertion of an edge between the twins. Using that result, we investigate the cir- cumstances under which inserting a new edge increases Kemeny's con- stant. In particular, we characterise the complete multipartite graphs without dominating vertices having the property that adding any new edge increases Kemeny's constant. We establish an analogous result for complete split graphs. We also prove that if a complete multi- partite graph has enough dominating vertices, then there is always a non-edge whose addition will decrease Kemeny's constant.