Nordhaus--Gaddum relations for degrees and connectivities under the $\delta$-complement

Abstract

The $\delta$-complement $G_{\delta }$ of a graph $G$ complements adjacency within each degree class and preserves adjacency between distinct degree classes. We establish sharp lower and upper additive and product Nordhaus--Gaddum bounds for the minimum degree, maximum degree, vertex connectivity, and edge connectivity of $G$ and $G_{\delta }$. We give explicit constructions attaining all stated sharp bounds.