View PDF HTML (experimental)

Abstract:Let $G$ be an $n$-vertex simple graph with adjacency matrix $A_G$. The complement rank of $G$ is defined as $\operatorname{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$, $$ \operatorname{rank}(A_G+I)\cdot\operatorname{rank}(A_{\overline G}+I) \ge n, \qquad \operatorname{rank}(A_G+I)+\operatorname{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 $$ \operatorname{rank}(A_G+I)\cdot\operatorname{rank}(A_{\overline G}+I) \le n^2, \qquad \operatorname{rank}(A_G+I)+\operatorname{rank}(A_{\overline G}+I) \le 2n $$ are tight by explicitly constructing, for every $n\ge 4$, graphs $G$ with $\operatorname{rank}(A_G+I)=\operatorname{rank}(A_{\overline G}+I)=n$.

Submission history

From: Quanyu Tang [view email]
[v1] Sun, 14 Sep 2025 17:48:58 UTC (9 KB)
[v2] Sun, 17 May 2026 10:09:52 UTC (11 KB)
[v3] Fri, 3 Jul 2026 15:01:28 UTC (11 KB)