On the normalized Shannon capacity of a union

Abstract

Let $G_1\times G_2$ denote the strong product of graphs $G_1$ and $G_2$, i.e. the graph on $V(G_1)\times V(G_2)$ in which $(u_1,u_2)$ and $(v_1,v_2)$ are adjacent if for each $i=1,2$ we have $u_i=v_i$ or $u_i{v}_i\in E(G_i)$. The Shannon capacity of $G$ is $c(G)={\lim }_{n\to \infty }\alpha (G^n{)}^{1/n}$, where $G^n$ denotes the $n$-fold strong power of $G$, and $\alpha (H)$ denotes the independence number of a graph $H$. The normalized Shannon capacity of $G$ is $C(G)=\frac{\log c(G)}{\log |V(G)|}$. Alon asked whether for every $\epsilon >0$ there are graphs $G$ and $G^{\prime }$ satisfying $C(G),C(G^{\prime })<\epsilon$ but with $C(G+G^{\prime })>1-\epsilon$. We show that the answer is no.

2 pages

Cited by in corpus (1)

• Observations on Graph Invariants with the Lovász $\vartheta$-Function