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.