The Independence Number of Self-complementary Graphs It is known for all that there are various lower bounds for the independence number of general graphs, such as Caro-Wei Bound, Hanson's Bound and Wilf's bound. Now my question is: as for self-complementary graphs, are there any better lowers bounds for the indenpendence number? More specifically, I wonder that if $G$ is a self-complementary graph with $4n$ vertices, is it true that its independence number $\alpha(G)$ is at least $n$?
 A: This is not the answer to the question, but it is too long for a commentary.
The considerations given here suggest that the $n$-boundary for self-complementary graphs of order $4n$ seems to be overestimated.
Let $q$ be a prime power and $q\equiv1\pmod{4}$.
The Paley graph $P(q)$ of order $q$  is a graph on $q$ vertices with two vertices adjacent if their difference is a square in the finite field $GF(q)$.
Paley graphs are self-complementary graphs.
It is known that the clique number of the Paley graph $P(17)$ is $3$.
(By the way, it follows that the Ramsey number $R(4, 4) = 18$.)
Since the independence number and the clique number of a self-complementary graph coincide, $\alpha(P(17))=3<[17/4]$.
It is also known that $\alpha(P(101))=5$ but $[101/4]=25$.
Moreover, $\alpha(P(q))=\sqrt{q}$ if $q$ is an even power of a prime.
See the articles Paley graph on Wolfram and on Wikipedia.
A: Let $r(n)$ denote the minimum, over all graphs $G$ of order $n$, of the quantity $\max\{\alpha(G),\omega(G)\}$, where $\alpha(G)$ is the independence number and $\omega(G)$ is the clique number; $r(n)\le C\log n$ by a classical result of Erdős. For $n\equiv0\text{ or }1\pmod4$ let $r_{sc}(n)$ be defined similarly but the minimum is taken over self-complementary graphs. Plainly $r_{sc}(n)\ge r(n)$.
On the other hand, $r_{sc}(4n)\le2r(n)$ and $r_{sc}(4n+1)\le2r(n)$. To see this, consider a graph $H$ of order $n$ with $\alpha(H),\omega(H)\le r(n)$. Let $H_1,H_2,H_3,H_4$ be vertex-disjoint graphs with $H_1\cong H_4\cong H$ and $H_2\cong H_3\cong\overline H$. Take the graph $H_1\cup H_2\cup H_3\cup H_4$ and add edges joining all vertices in $H_i$ to all vertices in $H_{i+1}$ for $i=1,2,3$. The resulting self-complementary graph $G$ of order $4n$ has
$$\alpha(G)=\max\{\alpha(H)+\alpha(H),\ \alpha(H)+\omega(H)\}\le2r(n).$$By adding another vertex to $G$ and edges joining the new vertex to all vertices in $H_1\cup H_4$, we get a self-complementary graph $G'$ of order $4n+1$ with $\alpha(G')=\alpha(G)\le2r(n)$.
For example, from $H=C_5$ we get self-complementary graphs $G$ and $G'$ with $n(G)=20$, $n(G')=21$, and $\alpha(G)=\alpha(G')=4$.
