Nordhaus--Gaddum type bounds for the complement rank

Abstract

Let $G$ be an $n$-vertex simple graph with adjacency matrix $A_G$. The 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_{\overline{G}}+I)\ge n,\mathrm{rank}(A_G+I)+\mathrm{rank}(A_{\overline{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_{\overline{G}}+I)\le n^2,\mathrm{rank}(A_G+I)+\mathrm{rank}(A_{\overline{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_{\overline{G}}+I)=n$.

arXiv comment10 pages; accepted for publication in Discrete Mathematics