## Abstract

Let G

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.

_{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 isC(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