Shannon number

Let α(G) denote the independence number of a graph G. Then the Shannon capacity Θ(G), sometimes also denoted c(G), of G is defined as Θ(G) = lim_(k->∞) [α(G□x...□x G_︸_k)]^(1/k), where □x denoted the graph strong product (Shannon 1956, Alon and Lubetzky 2006). The Shannon capacity is an important information theoretical parameter because it represents the effective size of an alphabet in a communication model represented by a graph G. Θ(G) is bounded from below by the independence number α(G)<=Θ(G) and from above by the Lovász number and Haemers number.

graph strong product | Haemers number | independence number | Lovász number | perfect graph | sandwich theorem