What is the lower bound for the sum of the independence numbers of a graph and its complement?

Question

The independence number $\alpha(G)$ of a graph $G$ is the cardinality of the largest independent vertex set.

My question is as stated in the title. We can observe from a path with $n$ vertices that its independence number is $\lceil \frac{n}{2} \rceil $ and its complement has independence number 2. So $\alpha(G)+\alpha(\overline G)=\lceil \frac{n}{2} \rceil +2$.

Are there graphs whose $\alpha(G)+\alpha(\overline G)$ is smaller than $\lceil \frac{|V(G)|}{2} \rceil +2$? Note that their upper bound is $|V(G)|+1$; and it can be seen in the link minimum independence number of graph G and the maximum independence number of G's complement?.

---

Note that the clique number of a graph is equal to the independence number of the complement graph.

Answer 1

Let $n=k^2$ and consider the complete $k$-partite graph $K_{k,k,\dots,k}$, whose complement is the disjoint union of $k$ copies of $K_k$.

• Its independence number is $k$ since the clique number of its complement is obviously $k$.
• Its own clique number is also $k$ – taking one vertex from each part yields a clique, but a set of $k+1$ vertices will have two vertices from the same part by the pigeonhole principle; these vertices will not be adjacent.

Thus for this graph on $n$ vertices $\alpha(G)+\alpha(\overline G)=2\sqrt n$. This construction easily generalises to non-square $n$, so we can achieve sums of $\lceil2\sqrt n\rceil$.