Symmetric graphs with respect to graph entropy

Seyed Saeed Changiz Rezaei¹ ; Ehsan Chiniforooshan²

¹1QB information Technology-Simon Fraser University, Vancouver, BC, Canada
²Google Inc., Waterloo, ON, Canada

The electronic journal of combinatorics, Tome 24 (2017) no. 1

Résumé

Let $F_G(P)$ be a functional defined on the set of all the probability distributions on the vertex set of a graph $G$. We say that $G$ is symmetric with respect to $F_G(P)$ if the uniform distribution on $V(G)$ maximizes $F_G(P)$. 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 characterize all graphs which are symmetric with respect to graph entropy. We show that a graph is symmetric with respect to graph entropy if and only if its vertex set can be uniformly covered by its maximum size independent sets. This is also equivalent to saying that the fractional chromatic number of $G$, $\chi_f(G)$, is equal to $\frac{n}{\alpha(G)}$, where $n = |V(G)|$ and $\alpha(G)$ is the independence number of $G$. Furthermore, given any strictly positive probability distribution $P$ on the vertex set of a graph $G$, we show that $P$ is a maximizer of the entropy of graph $G$ if and only if its vertex set can be uniformly covered by its maximum weighted independent sets. We also show that the problem of deciding if a graph is symmetric with respect to graph entropy, where the weight of the vertices is given by probability distribution $P$, is co-NP-hard.

Détail

DOI : 10.37236/5642

Classification : 05C15, 05C85, 05C22
Mots-clés : graph entropy, fractional chromatic number