On the Normalized Shannon Capacity of a Union

Source abstract

Let G 1 × G 2 denote the strong product of graphs G 1 and G 2 , that is, the graph on V ( G 1 ) × 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 ∈ E ( G i ). The Shannon capacity of G is c ( G ) = lim n → ∞ α( G n ) 1/ n , where G n denotes the n -fold strong power of G , and α( H ) denotes the independence number of a graph H . The normalized Shannon capacity of G is $$C(G) = \ffrac {\log c(G)}{\log |V(G)|}.$$ Alon [1] asked whether for every ε < 0 there are graphs G and G ′ satisfying C ( G ), C ( G ′) < ε but with C ( G + G ′) > 1 − ε. We show that the answer is no.