Complementary Graph Entropy, AND Product, and Disjoint Union of Graphs

Abstract

In the zero-error Slepian-Wolf source coding problem, the optimal rate is given by the complementary graph entropy $\overline{H}$ of the characteristic graph. It has no single-letter formula, except for perfect graphs, for the pentagon graph with uniform distribution $G_5$, and for their disjoint union. We consider two particular instances, where the characteristic graphs respectively write as an AND product $\wedge$, and as a disjoint union $\bigsqcup$. We derive a structural result that equates $\overline{H}(\wedge \cdot )$ and $\overline{H}(\bigsqcup \cdot )$ up to a multiplicative constant, which has two consequences. First, we prove that the cases where $\overline{H}(\wedge \cdot )$ and $\overline{H}(\bigsqcup \cdot )$ can be linearized coincide. Second, we determine $\overline{H}$ in cases where it was unknown: products of perfect graphs; and $G_5\wedge G$ when $G$ is a perfect graph, using Tuncel et al.'s result for $\overline{H}(G_5\bigsqcup G)$. The graphs in these cases are not perfect in general.