Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer 1

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|improve this answer
    
New question posted here: math.stackexchange.com/questions/468165/a-question-on-graphs –  J.A Aug 15 '13 at 10:32
1  
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). –  J.A Aug 15 '13 at 11:36
    
Is there such a $G$ that is self-complementary? –  J.A 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
show 1 more comment

Your Answer

 
discard

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.