Nordhaus--Gaddum type bounds for the complement rank

Summary · qwen2.5:32b

The paper establishes Nordhaus--Gaddum type bounds for the complement rank of a graph, proving that for any graph \(G\), the product and sum of the complement ranks of \(G\) and its complement \(\overline{G}\) have specific lower bounds (\(n\) and \(n+1\), respectively), with conditions for equality. The authors also construct examples demonstrating that the upper bounds for these measures, \(n^2\) for the product and \(2n\) for the sum, are tight for graphs of order \(n \ge 4\).

Suggested post angle

Learn about Nordhaus--Gaddum type bounds for the complement rank in graph theory!

Excerpt

arXiv:2509.11368v3 Announce Type: replace 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$.