Entropy of symmetric graphs

DOI10.1016/J.DISC.2015.09.020MaRDI QIDQ898092zbMATH OpenOpenAlexFDO

Authors Seyed Saeed Changiz Rezaei, Chris Godsil

Publication date 8 December 2015

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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^{\ast }$ 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.

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

Cites work

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

Cited in

(6)

• Perfect couples of graphs
• scientific article; zbMATH DE number 891075 (Why is no real title available?)
• 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)