Entropy of symmetric graphs

DOI10.1016/J.DISC.2015.09.020zbMATH Open1327.05101arXiv1311.6561OpenAlexW1881477017MaRDI QIDQ898092FDOQ898092

Authors: Seyed Saeed Changiz Rezaei, Chris Godsil 

Publication date: 8 December 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A graph $G$ is called emph{symmetric with respect to a functional $F_G(P)$} defined on the set of all the probability distributions on its vertex set 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.

Full work available at URL: https://arxiv.org/abs/1311.6561

Recommendations

• Symmetric graphs with respect to graph entropy
• Perfect couples of graphs
• Capacities of graphs and \(2\)-matchings
• Perfect graphs and graph entropy: An updated survey
• Graphs that Split Entropies

zbMATH Keywords

graph entropyperfect graphsfractional chromatic numbervertex packing polytope

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Perfect graphs (05C17)

Cites Work

• Title not available (Why is that?)
• Matching theory
• Normal hypergraphs and the perfect graph conjecture
• Title not available (Why is that?)
• On certain polytopes associated with graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A characterization of perfect graphs
• On the Size of Separating Systems and Families of Perfect Hash Functions
• Fredman–Komlós bounds and information theory
• Blocking and anti-blocking pairs of polyhedra
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graphs that Split Entropies
• Two-step encoding for finite sources
• Perfect graphs and graph entropy: An updated survey
• New bounds for perfect hashing via information theory
• Perfect couples of graphs
• Capacities of graphs and \(2\)-matchings
• Title not available (Why is that?)
• Entropy of symmetric graphs

Cited In (6)

• Perfect couples of graphs
• Title not available (Why is that?)
• Hosoya entropy of fullerene graphs
• Graph pairs and their entropies: Modularity problems
• Symmetric graphs with respect to graph entropy
• Entropy of symmetric graphs

This page was built for publication: Entropy of symmetric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q898092)