zbMATH — the first resource for mathematics

On the Shannon capacity of a graph. (English) Zbl 0395.94021
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}\).

05C99 Graph theory
94A17 Measures of information, entropy
Full Text: DOI