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$?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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.
-
$\begingroup$ New question posted here: math.stackexchange.com/questions/468165/a-question-on-graphs $\endgroup$– TurboCommented Aug 15, 2013 at 10:32
-
1$\begingroup$ 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. $\endgroup$– JernejCommented Aug 15, 2013 at 11:32
-
$\begingroup$ I meant $=1$ (of course it does not make sense). $\endgroup$– TurboCommented Aug 15, 2013 at 11:36
-
$\begingroup$ Is there such a $G$ that is self-complementary? $\endgroup$– TurboCommented Aug 15, 2013 at 12:06
-
$\begingroup$ You mean a self complementary graph $G$ so that the above quantity is $0$? $\endgroup$– JernejCommented Aug 15, 2013 at 12:53