For $G$ a graph, let $\alpha(G)$ be its independence number and $\Theta(G)=\lim\_n \sqrt[n]{\alpha(G^{\boxtimes})}$ its [Shannon capacity](https://en.wikipedia.org/wiki/Lov%C3%A1sz_number#Shannon_capacity_of_a_graph), where $\boxtimes$ denotes [strong product](https://en.wikipedia.org/wiki/Strong_graph_product).


Consider graphs $G$ and $H$ satisfying $\alpha(G)=\Theta(G)$ and $\alpha(H)=\Theta(H)$. For example, $G$ and $H$ could be perfect, but the more interesting situations arise when neither of them is perfect.


**Question:** Does this assumption imply  

(1) $\alpha(G\boxtimes H) = \alpha(G)\alpha(H)$ ?  

(2) $\Theta(G\boxtimes H) = \Theta(G)\Theta(H)$ ?  

(3) $\Theta(G + H) = \Theta(G) + \Theta(H)$ ?


Here, $G+H$ stands for the disjoint union of $G$ and $H$.


If my reasoning is correct, then (1) and (2) are equivalent and imply (3).


As far as I can see, neither the work of [Haemers](https://ieeexplore.ieee.org/document/1056027) nor the results of [Alon](http://www.cs.umd.edu/%7Egasarch/const_ramsey/alon98.pdf) have anything directly to say about these questions. But then again, I am not an expert on this, so I might have missed something obvious.


*Edit* (see Will Traves' answer): Actually, I am specifically interested in those $G$ and $H$ which are [well-covered](https://en.wikipedia.org/wiki/Well-covered_graph).


*Edit*: The paper is [here](https://arxiv.org/abs/1212.4084).



graphs with independence number = Shannon capacity
By now, we have been able to resolve this question, and our [revised paper](http://arxiv.org/abs/1212.4084) contains a proof showing that the answer to all three questions is negative in a very strong sense. Let me provide a brief summary here and refer to the paper for more details.


What we show is this: there exist graphs $G$ and $H$ with $\alpha(G)=\Theta(G)$ and $\alpha(H)=\vartheta(H)$ which violate all three desired inequalities. Note that the property $\alpha(H)=\vartheta(H)$ is even stronger than the required property $\alpha(H)=\Theta(H)$.


The construction crucially relies on the definitions and results on hypergraphs discussed in our paper and on results of Haemers. We have partially translated it into pure graph-theoretic terms, but it does not seem possible to do so completely.


The counterexample turns out to be the following:


* $G$ is a $108$-regular graph on $220$ vertices. The vertices correspond to the $3$-element subsets of $\{1,\ldots,12\}$ and two such vertices are adjacent whenever the subsets intersect in exactly one element. This graph was considered by Haemers, who showed that $\alpha(G) = \Theta(G) < \vartheta(G)$, and this property is the most important ingredient for us.
* $H$ is a graph constructed from the complement of $G$ which turns out to have $1131460$ vertices.


I suspect that a similar construction can be carried out starting with any graph $G$ having the property that $\alpha(G) = \Theta(G) < \vartheta(G)$, but we haven't checked all the details of this.


