Kemeny's constant κ(G) of a connected undirected graph G can be interpreted as the expected transit time between two randomly chosen vertices for the Markov chain associated with G. In certain cases, inserting a new edge into G has the counter-intuitive effect of increasing the value of κ(G). In the current work we identify a large class of graphs exhibiting this “paradoxical” behavior – namely, those graphs having a pair of twin pendent vertices. We also investigate this phenomenon in the context of random graphs, showing that it occurs for almost all connected planar graphs. To establish these results, we make use of a connection between Kemeny's constant and the resistance distance of graphs.
This item's license is: Attribution 4.0 International