2013/11/26 by Seyed Saeed Changiz Rezaei, Chris Godsil, Rezaei, Seyed Saeed Changiz +1 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1311.6561
20 pages, 3 figures
arxiv created 2013/11/26 · openalex publication_date 2013/11/26 · arxiv updated 2013/11/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G is called symmetric with respect to a functional FG(P) defined on the set of all the probability distributions on its vertex set if the distribution P^* maximizing FG(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.