The Shannon capacity of a graph is defined as
$$\Theta(G) = \sup\_k \sqrt[k]{\alpha(G^k)}.$$


So, $\alpha(G) \leq \Theta(G)$ but $\Theta(G)$ can be strictly greater than $\alpha(G)$. I am wondering if there is any upper bound based on the independence number itself? Specifically, are there graphs where $\Theta(G) \geq \alpha(G) + 1$? It seems like the structure of the strong product limits how much the independence number can grow. The independence number would have to grow pretty quick just for $\sqrt[k]{\alpha(G^k)}$ to get up to $\alpha(G) + 1$ for some $k$.



Upper bound on Shannon capacity based on independence number
Self-complementary vertex-transitive graphs have Shannon capacity $\sqrt n$, so if this number is far from $\alpha$, then you have what you're looking for.


Paley graphs have this property, and as you can see here, there are examples for which $\alpha$ is indeed much less than the Shannon capacity.


<http://www.research.ibm.com/people/s/shearer/indpal.html>


<http://mathworld.wolfram.com/PaleyGraph.html>


<http://mathworld.wolfram.com/ShannonCapacity.html>


