MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Do there exist a family of graphs with the property: $$\left|\alpha\left({G \boxtimes \bar{G}}\right) - \alpha\left({\overline{G \boxtimes \bar{G}}}\right)\right| = O(\log(N_{G}))$$ where $G$ is the graph, $\bar{G}$ is its complement, $\boxtimes$ denotes the strong product, $\alpha(G)$ denotes the independence number of $G$ and $N_{G}$ is the number of vertices of $G$?

share|cite|improve this question
up vote 3 down vote accepted

Since $$\alpha(\overline{K_n \boxtimes \overline{K_n}}) = n$$ and $$\alpha(K_n \boxtimes \overline{K_n}) = n$$ it follows that the family of complete graphs satisfies your assumptions.

To see the first equality observe that $K_n \boxtimes \overline{K_n}$ is the disjoint union of $n$ copies of $K_n.$ Hence in the complement every disjoint $K_n$ is an independent set any pair of vertices from disjoint copies of $K_n$ is adjacent.

share|cite|improve this answer
New question posted here: – Turbo Aug 15 '13 at 10:32
I've edited my answer so that you can see as to why the stated equality holds. Also, having $\alpha(H) =0 $ makes no sense. – Jernej Aug 15 '13 at 11:32
I meant $=1$ (of course it does not make sense). – Turbo Aug 15 '13 at 11:36
Is there such a $G$ that is self-complementary? – Turbo Aug 15 '13 at 12:06
You mean a self complementary graph $G$ so that the above quantity is $0$? – Jernej Aug 15 '13 at 12:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.