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) satisfies α(G)<=Θ(G).

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