1979/01/01 by László Lovász · 3 citations
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Graph theory and applications #Graph Labeling and Dimension Problems #Pentagon #Transitive relation #Combinatorics #Graph #Mathematics #Vertex (graph theory) #Discrete mathematics #Automorphism group #Automorphism
paper · doi:10.1109/tit.1979.1055985
openalex publication_date 1979/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
It is proved that the Shannon zero-error capacity of the pentagon is√(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√(5).