Let
denote the independence number of a graph
. Then the Shannon capacity , sometimes also denoted , of is defined as

where
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 (Alon 1998).

satisfies

The Shannon capacity is in general very difficult to calculate (Brimkov et al. 2000). In fact, the Shannon capacity of the cycle
graph
was not determined as
until 1979 (Lovász 1979), and the Shannon capacity of is perhaps one of the most notorious open problems in extremal
combinatorics (Bohman 2003).

Alon, N. "Explicit Ramsey Graphs and Orthonormal Labelings." Elec. J. Combin.1, No. R12, 1-8, 1994.Alon, N. "The
Shannon Capacity of a Union." Combinatorica18, 301-310, 1998.Alon,
N. and Lubetzky, E. "The Shannon Capacity of a Graph and the Independence Numbers
of Its Powers." IEEE Trans. Inform. Th.52, 2172-2176, 2006.Bohman,
T. "A Limit Theorem for the Shannon Capacities of Odd Cycles. I." Proc.
Amer. Math. Soc.131, 3559-3569, 2003.Bohman, T. and Holzman,
R. "A Nontrivial Lower Bound on the Shannon Capacities of the Complements of
Odd Cycles." IEEE Trans. Inform. Th.49, 721-722, 2003.Brimkov,
V. E.; Codenotti, B.; Crespi, V.; and Leoncini, M. "On the Lovász
Number of Certain Circulant Graphs." In Algorithms
and Complexity. Papers from the 4th Italian Conference (CIAC 2000) Held in Rome,
March 1-3, 2000 (Ed. G. Bongiovanni, G. Gambosi, and R. Petreschi).
Berlin: Springer-Verlag, pp. 291-305, 2000.Haemers, W. "An
Upper Bound for the Shannon Capacity of a Graph." In Algebraic Methods in
Graph Theory. Szeged, Hungary: pp. 267-272, 1978.Haemers, W.
"On Some Problems of Lovász Concerning the Shannon Capacity of a Graph."
IEEE Trans. Inform. Th.25, 231-232, 1979.Knuth, D. E.
"The Sandwich Theorem." Electronic J. Combinatorics1, No. 1,
A1, 1-48, 1994. http://www.combinatorics.org/Volume_1/Abstracts/v1i1a1.html.Lovász,
L. "On the Shannon Capacity of a Graph." IEEE Trans. Inform. Th.IT-25,
1-7, 1979.Riis, S. "Graph Entropy, Network Coding and Guessing."
27 Nov 2007. http://arxiv.org/abs/0711.4175v1.Schrijver,
A. "A Comparison of the Delsarte and Lovász Bounds." IEEE Trans.
Inform. Th.25, 425-429, 1979.Shannon, C. E. "The
Zero-Error Capacity of a Noisy Channel." IRE Trans. Inform. Th.2,
8-19, 1956.van Lint, J. H. and Wilson, R. M. A
Course in Combinatorics. New York: Cambridge University Press, 1992.