A Nordhaus–Gaddum Problem for the Spectral Gap of a Graph

ABSTRACT Let be a graph on vertices, with complement . The spectral gap of the transition probability matrix of a random walk on is used to estimate how fast the random walk becomes stationary. We prove that the larger spectral gap of and is . Moreover, if all degrees are and , then the larger spectral gap of and is . We also show that if the maximum degree is or if is a join of two graphs, then the spectral gap of is . Finally, we provide a family of connected graphs with connected complements such that the larger spectral gap of and is .