We, generalize the concept of perfect graphs in terms of additivity of a functional called graph entropy. The latter is an information theoretic functional on a graph G with a probability distribution P on its vertex set. For any fixed P it is sub-additive with respect to graph union. The entropy of the complete graph equals the sum of those of G and its complement GBAR iff G is perfect. We generalize this recent result to characterize all the cases when the sub-additivity of graph entropy holds with equality.
PERFECT COUPLES OF GRAPHS / Korner, Janos; G�bor, Simonyi; Zsolt, Tuza. - In: COMBINATORICA. - ISSN 0209-9683. - STAMPA. - 12:2(1992), pp. 179-192. [10.1007/bf01204721]
PERFECT COUPLES OF GRAPHS
KORNER, JANOS;
1992
Abstract
We, generalize the concept of perfect graphs in terms of additivity of a functional called graph entropy. The latter is an information theoretic functional on a graph G with a probability distribution P on its vertex set. For any fixed P it is sub-additive with respect to graph union. The entropy of the complete graph equals the sum of those of G and its complement GBAR iff G is perfect. We generalize this recent result to characterize all the cases when the sub-additivity of graph entropy holds with equality.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
