Lovász, László On the Shannon capacity of a graph. (English) Zbl 0395.94021 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) Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 16 ReviewsCited in 326 Documents MSC: 05C99 Graph theory 94A17 Measures of information, entropy Keywords:Shannon zero error capacity; pentagon; vertex transitive automorphism group; Petersen graph; self-complementary graph PDF BibTeX XML Cite \textit{L. Lovász}, IEEE Trans. Inf. Theory 25, 1--7 (1979; Zbl 0395.94021) Full Text: DOI