Entropy of symmetric graphs.

Let F G ( P ) be a functional defined on the set of all the probability distributions on the vertex set of a graph G . We say that G is symmetric with respect to F G ( P ) if the distribution P ∗ maximizing F G ( P ) is uniform on V ( G ) . Using the combinatorial definition of the entropy of a graph in terms of its vertex packing polytope and the relationship between the graph entropy and fractional chromatic number, we prove that vertex-transitive graphs are symmetric with respect to graph entropy. As the main result of this paper, we prove that a perfect graph is symmetric with respect to graph entropy if and only if its vertices can be covered by disjoint copies of its maximum-size clique. Particularly, this means that a bipartite graph is symmetric with respect to graph entropy if and only if it has a perfect matching. [ABSTRACT FROM AUTHOR]