학술논문
Symmetric graphs with respect to graph entropy.
Document Type
Journal
Author
Changiz Rezaei, Seyed Saeed (3-SFR) AMS Author Profile; Chiniforooshan, Ehsan (3-GOOGLE) AMS Author Profile
Source
Subject
05 Combinatorics -- 05C Graph theory
05C72Fractional graph theory, fuzzy graph theory
05C75Structural characterization of families of graphs
05C72
05C75
Language
English
Abstract
Summary: ``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 {\it 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 the 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.''