Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646642 | Discrete Mathematics | 2016 | 9 Pages |
Let FG(P)FG(P) be a functional defined on the set of all the probability distributions on the vertex set of a graph GG. We say that GG is symmetric with respect to FG(P)FG(P) if the distribution P∗P∗ maximizing FG(P)FG(P) is uniform on V(G)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.