{"id":"arxiv/2606.12751","url":"https://arxiv.org/abs/2606.12751","tags":["math.CO"],"score":0,"title":"Nordhaus-Gaddum upper bounds for graph connectivity parameters","domain":"math.CO","source":"arxiv","authors":["Mark Kempton","Xavier Zaitzeff","Sibi Muthuprakash"],"reviews":0,"subject":"math.CO","summary":"We examine upper bounds on Nordhaus-Gaddum type problems for parameters related to graph connectivity. Our main result is that for a graph $G$ on $n$ vertices where both $G$ and its complement $G^c$ are connected, then the sum of the algebraic connectivity of $G$ and the algebraic connectivity of $G^c$ cannot exceed $n-3$ (with finitely many exceptions with a small number of vertices). We obtain similar results for the isoperimetric number of a graph, and explore similar Nordhaus-Gaddum type questions for the Cheeger constant and the second eigenvalue of the normalized Laplacian matrix.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-10","reactions":{}}