Abstract
Let G1 × G2 denote the strong product of graphs G1 and G2, that is, the graph on V(G1) × V(G2) in which (u1, u2) and (v1, v2) are adjacent if for each i = 1, 2 we have ui = vi or uivi ∈ E(Gi). The Shannon capacity of G is c(G) = limn → ∞ α(Gn)1/n , where Gn 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) = 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.
C(G) = 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.
Original language | English |
---|---|
Pages (from-to) | 766-767 |
Number of pages | 2 |
Journal | Combinatorics, Probability and Computing |
Volume | 25 |
Issue number | 5 |
Early online date | 3 Mar 2016 |
DOIs | |
Publication status | Published - 1 Sept 2016 |
Keywords
- Shannon capacity