Nordhaus--Gaddum type bounds for the complement rank

Let $G$ be an $n$-vertex simple graph with adjacency matrix $A_G$. The \emph{complement rank} of $G$ is defined as $\mathrm{rank}(A_G+I)$, where $I$ is the identity matrix. In this paper we study Nordhaus–Gaddum type bounds for the complement rank. We prove that for every graph $G$, $$\mathrm{rank}(A_G+I)\cdot \mathrm{rank}(A_{\bar{G}}+I)\ge n,\mathrm{rank}(A_G+I)+\mathrm{rank}(A_{\bar{G}}+I)\ge n+1,$$ with the equality cases characterized. We further obtain strengthened multiplicative lower bounds under additional structural assumptions. Finally, we show that the trivial upper bounds $$\mathrm{rank}(A_G+I)\cdot \mathrm{rank}(A_{\bar{G}}+I)\le n^2,\mathrm{rank}(A_G+I)+\mathrm{rank}(A_{\bar{G}}+I)\le 2n$$ are tight by explicitly constructing, for every $n\ge 4$, graphs $G$ with $\mathrm{rank}(A_G+I)=\mathrm{rank}(A_{\bar{G}}+I)=n$.