ON THE SHANNON CAPACITY OF A GRAPH
ON THE SHANNON CAPACITY OF A GRAPH
复制标题
DOI：
10.1109/tit.1979.1055985
复制
发表时间：
1979-01-01
影响因子：
2.5
通讯作者：
LOVASZ, L
中科院分区：
文献类型：
--
作者：
LOVASZ, L
证明了五边形的香农零误差能力为。然后将该方法推广以获得任意图容量的上限。引入了一个特征良好且在某种意义上易于计算的函数，该函数从上方限制容量并等于大量情况下的容量。对特殊图的容量进行了一些研究；例如，Petersen 图的容量为 4，而具有 n 个点且具有顶点传递自同构群的自补图也具有容量。
It is proved that the Shannon zero-error capacity of the pentagon is. 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.