Numerical invariants for a graph or its complement that are bounded by some constant

Question

I'm looking for numerical graph invariants that are bounded by a constant either for a graph $G$ or its complement $\bar{G}$. (The complement graph $\bar{G}$ has the same set of vertices as $G$ but the edges are complemented.) More specifically I’m looking for what numerical “Invariant $X$” is out there for which the following statement is true:

“Invariant $X$ is bounded by a constant $c$ either for $G$ or $\bar{G}$”.

One example is diameter $d(G)$ of a graph $G$ where it is known that:

"Either $d(G) \leq 3$ or $d(\bar{G}) \leq 3$"

(Reference: F. Harary, R. W. Robinson: The diameter of a graph and its complement , The American Mathematical Monthly, Vol. 92, No. 3. (Mar., 1985), pp. 211-212”)

My question is what other such numerical graph invariants are out there? I looked at the list of invariants on wikipedia but there was no mention of such bound on their respective pages. Again, all I’m interested is that the condition holds for either $G$ or its complement $\bar{G}$ and not necessarily for both.

Answer 1

Let $c(G)$ be the number of connected components of $G$. Then for all graphs $G$, $$ c(G)=1 \text{ or } c(\overline{G})=1. $$

Here is a slightly more interesting family of examples. For a fixed integer $k$, define $d_k(G)$ to be the number of degree-$k$ vertices of $G$.

Claim. For all graphs $G$, $$d_k(G) \leq 2k \text{ or } d_k(\overline{G}) \leq 2k. $$

Proof. Suppose that $G$ contains more than $2k$ degree-$k$ vertices. Let $X$ be a set of degree-$k$ vertices of $G$ with $|X|=2k+1$. Let $N_G(X)$ be the neighbours of $X$ in $G$. Let $Y$ be the set of degree-$k$ vertices in $\overline{G}$. Since the vertices in $V(G) \setminus N_G(X)$ are not adjacent to any vertex in $X$, it follows that $Y \subseteq N_G(X)$. Towards a contradiction, suppose $|Y| \geq 2k+1$. Since $|X|=2k+1$, each vertex in $Y$ must send at least $k+1$ edges (in $G$) to $X$. Thus, there are at least $(2k+1)(k+1)$ edges between $N_G(X)$ and $X$. On the other hand, the number of edges between $X$ and $N_G(X)$ is at most $k|X|=k(2k+1)$, so we have a contradiction.

Answer 2

Another one: girth. By Ramsey's theorem, for every graph $G$ on six or more vertices, either it or its complement has girth at most three.

Answer 3

There are a lot of properties which $G$ and $\overline{G}$ both have them: number of vertices (edges), automorphism group, and etc. So, naturally this question is interesting for me. I want to mention a spectral property. Let $G$ be a graph with $n$ vertices, and $\rho(G)$ denotes the largest eigenvalue of the adjacency matrix of $G$. Then we have: $$\rho(G)\geq \frac{n-1}{2}\; \; \text{or}\;\; \rho(\overline{G})\geq \frac{n-1}{2}.$$

I will give the simplified proof for the above fact.

For any $n\times n$ Hermitian matrices $A$ and $B$, we have: $$\lambda_i(A+B)\leq \lambda_j(A)+\lambda_{i-j+1}(B),\;\; n\geq i\geq j\geq 1,$$ where, $\lambda_i(A)$ denotes the $i$th greatest eigenvalue of the matrix $A$. Now, for graph $G$, let $A$ be the adjacency matrix of $G$ and $B$ be the adjacency matrix of $\overline{G}$. Since we have $A+B=J-I$, which is the adjacency matrix of complete graph, the result is clear.