부산대학교 도서관

Summary: ``Let $F_G(P)$ be a functional defined on the set of all theprobability distributions on the vertex set of a graph $G$. We say that$G$ is {\it symmetric with respect to} $F_G(P)$ if the uniformdistribution on $V(G)$ maximizes $F_G(P)$. Using the combinatorialdefinition of the entropy of a graph in terms of its vertex packingpolytope and the relationship between the graph entropy and fractionalchromatic number, we characterize all graphs which are symmetric withrespect to graph entropy. We show that a graph is symmetric withrespect to graph entropy if and only if its vertex set can be uniformlycovered by its maximum size independent sets. This is also equivalentto saying that the fractional chromatic number of $G$, $\chi_f(G)$, isequal to $\frac{n}{\alpha(G)}$, where $n=|V(G)|$ and $\alpha(G)$ is theindependence number of $G$. Furthermore, given any strictly positiveprobability distribution $P$ on the vertex set of a graph $G$, we showthat $P$ is a maximizer of the entropy of the graph $G$ if and only ifits vertex set can be uniformly covered by its maximum weightedindependent sets. We also show that the problem of deciding if a graphis symmetric with respect to graph entropy, where the weight of thevertices is given by probability distribution $P$, is co-NP-hard.''