Complete multipartite graphs and Braess edges

Given an irreducible stochastic matrix T, Kemeny's constant kappa(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 circumstances under which inserting a new edge increases Kemeny's constant. 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 multipartite graph has enough dominating vertices, then there is always a non-edge whose addition will decrease Kemeny's constant. (C) 2019 Elsevier Inc. All rights reserved.