Shannon capacity of $C_5$ with two isolated vertices Let $G$ consist of a cycle of length $5$ and two isolated vertices. Show that the Shannon capacity $S(G)$ of $G$ satisfies $S(G) = \sqrt{5} + 2$ and conclude that there is no finite $k$ such that $S(G) = (\alpha(G^k))^{1/k}$ where $\alpha(G)$ is the independence number of $G$.
Any ideas how to solve this problem? For the first part of the problem, I know that $S(C_5)=\sqrt5$ and it seems intuitive that adding two isolated vertices would increase the $S(G)$ by 2, but not sure how to show this rigorously.
For the second part, I found that $\alpha(G) = 4$ since we can choose two vertices from $C_5$ and the two isolated vertices, but I'm not sure how to consider $(\alpha(G^k))^{1/k}$.
 A: If $G = C_5 \cup 2 K_1$ - a cycle plus two isolated vertices - then, interestingly enough, we can expand $G^{\boxtimes k}$ using the binomial theorem.
A vertex in $G^{\boxtimes k}$ is a $k$-tuple $(v_1, v_2, \dots, v_k)$ where each $v_i$ is a vertex in $G$. For each element $x = (x_1, x_2, \dots, x_k) \in \{\text{cycle}, 1, 2\}^k$ consider the set of vertices of $G^{\boxtimes k}$ such that, for $i=1,\dots,k$:

*

*If $x_i = \text{cycle}$ then $v_i$ is one of the five cycle vertices of $G$.

*If $x_i = 1$ then $v_i$ is the first isolated vertex of $G$.

*If $x_i = 2$ then $v_i$ is the second isolated vertex of $G$.

This set of vertices induces a connected component in $G^{\boxtimes k}$ which is isomorphic to $C_5^{\boxtimes r}$, where $r$ is the number of coordinates of $x$ equal to "$\text{cycle}$". For each $r$, there are $\binom{k}{r} 2^r$ ways to choose an $x$ with $r$ coordinates equal to "$\text{cycle}$", so we can write $G^{\boxtimes k}$ as the disjoint union
$$
   G^{\boxtimes k} = \bigcup_{r=0}^k \binom kr 2^r C_5^{\boxtimes r}
$$
and this tells us that
$$
   \alpha(G^{\boxtimes k}) = \sum_{r=0}^\infty \binom kr 2^r \alpha(C_5^{\boxtimes r}).
$$
If $\alpha(C_5^{\boxtimes r})$ were exactly equal to $5^{r/2}$ for all $r$, then by the binomial theorem we'd get $\alpha(G^{\boxtimes k}) = (2 + \sqrt 5)^k$. This is not exactly true - we have $\alpha(C_5^{\boxtimes r}) = 5^{r/2}$ for even $r$ and $\alpha(C_5^{\boxtimes r}) = 2 \cdot 5^{(r-1)/2}$ for odd $r$. The odd-$r$ value is $\frac{2}{\sqrt 5}$ of the even-$r$ value, so we have an inequality
$$
    \frac{2}{\sqrt 5} (2+\sqrt5)^k \le \alpha(G^{\boxtimes k}) \le (2+\sqrt5)^k
$$
which is still enough to conclude that $S(G) = 2 + \sqrt 5$.
