# 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}$$.

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