On the Shannon capacity of a graph. (English) Zbl 0395.94021

Lovász, László

IEEE Trans. Inf. Theory 25, 1-7 (1979).

Author’s summary: It is proved that the Shannon zero-error capacity of the pentagon is \(\sqrt{5}\). The method is then generalized to obtain upper bounds on the capacity of an arbitrary graph. A well-characterized, and in a sense easily computable, function is introduced which bounds the capacity from above and equals the capacity in a large number of cases. Several results are obtained on the capacity of special graphs; for example, the Petersen graph has capacity four and a self-complementary graph with \(n\) points and with a vertex-transitive automorphism group has capacity \(\sqrt{5}\).

Reviewer: Geoffrey Grimmett (Cambridge)

MSC:

05C99	Graph theory
94A17	Measures of information, entropy

Keywords:

Shannon zero error capacity; pentagon; vertex transitive automorphism group; Petersen graph; self-complementary graph