کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646642 | 1342309 | 2016 | 9 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 339, Issue 2, 6 February 2016, Pages 475–483