Nordhaus--Gaddum type bounds for the complement rank

Let G be an n-vertex simple graph with adjacency matrix AG. The complement rank of G is defined as rank(AG+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, rank(AG+I)(AG+I) ≥ n, rank(AG+I)+rank(AG+I) ≥ 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 rank(AG+I)(AG+I) ≤ n², rank(AG+I)+rank(AG+I) ≤ 2n are tight by explicitly constructing, for every n≥ 4, graphs G with rank(AG+I)=rank(AG+I)=n.