On Complementary Graph Entropy

It has been recently discovered that complementary graph entropy characterizes (and offers new insights into) the minimum asymptotic rate for zero-error source coding with decoder side information. This paper presents new results that build on and complement this discovery. Specifically, i) previously unknown subadditivity properties of complementary graph entropy are derived, and ii) zero-error coding rates are characterized in terms of complementary graph entropy for two multiterminal coding scenarios. For both scenarios, the rate characterization implies no rate loss relative to point-to-point source coding.