Bounds on Kemeny's constant of a graph and the Nordhaus-Gaddum problem

Sooyeong Kim, Neal Madras, Ada Chan +3

We study Nordhaus-Gaddum problems for Kemeny's constant $\mathcal{K}(G)$ of a connected graph $G$. We prove bounds on $\min \{\mathcal{K}(G),\mathcal{K}(\overline{G})\}$ and the pro…