Shannon capacity of $C_5$ with two isolated vertices

Question

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}$.

Answer 1

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$.

Answer 2

$\color{blue}{\text{Maybe a bit off topic, I wrote this answer to explain what these nouns are.}}$

---

Some definitions

ShannonCapacity

Wikipedia link WoframMathWorld link

formula is $\Theta(G)=\sup \limits_{k }\left[\alpha(\underbrace{G ⊠ \cdots ⊠G)}_k \right] ^{1 / k}$

where $⊠$ here means do strong product of graphs , $\alpha(G)$ here means IndependentNumber of graph $G$

IndependentNumber

a lower bound on the Shannon capacity of the graph.

usually refer to "The (upper) vertex independence number of a graph" ,i.e., the size of a maximum independent vertex set

for Cycle graph $C_n$, the formula is $\lfloor n / 2\rfloor$

Lovász number

an upper bound on the Shannon capacity of the graph.

for Cycle graph $C_n$, the formula is $\vartheta\left(C_n\right)= \begin{cases}\frac{n \cos (\pi / n)}{1+\cos (\pi / n)} & \text { for odd } n \\ \frac{n}{2} & \text { for even } n\end{cases}$

for Cycle graph $C_5$, $\frac{5 \cos (\pi / 5)}{1+\cos (\pi / 5)}=\sqrt{5}$,the Lovász number bound is tight, so the Shannon capacity of the $5$-cycle is exactly $\sqrt{5}$