Full Record

New Search | Similar Records

Author
Title Entropy and Graphs
URL
Publication Date
University/Publisher University of Waterloo
Abstract The entropy of a graph is a functional depending both on the graph itself and on a probability distribution on its vertex set. This graph functional originated from the problem of source coding in information theory and was introduced by J. K\"{o}rner in 1973. Although the notion of graph entropy has its roots in information theory, it was proved to be closely related to some classical and frequently studied graph theoretic concepts. For example, it provides an equivalent definition for a graph to be perfect and it can also be applied to obtain lower bounds in graph covering problems. In this thesis, we review and investigate three equivalent definitions of graph entropy and its basic properties. Minimum entropy colouring of a graph was proposed by N. Alon in 1996. We study minimum entropy colouring and its relation to graph entropy. We also discuss the relationship between the entropy and the fractional chromatic number of a graph which was already established in the literature. 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. Furthermore, we show that a bipartite graph is symmetric with respect to graph entropy if and only if it has a perfect matching. As a generalization of this result, we characterize some classes of symmetric perfect graphs with respect to graph entropy. Finally, we prove that the line graph of every bridgeless cubic graph is symmetric with respect to graph entropy.
Subjects/Keywords Entropy; Probability distribution; Graphs; Fractional Chromatic Number; Vertex packing polytope; Perfect Graphs; Line Graphs
Language en
Country of Publication ca
Record ID handle:10012/8173
Repository waterloo
Date Retrieved
Date Indexed 2019-06-26

Sample Search Hits | Sample Images

…21 3.5 Entropy of Some Special Graphs . . . . . . . . . . . . . . . . . . . . . . . . 23 3.6 Graph Entropy and Fractional Chromatic Number . . . . . . . . . . . . . . 28 3.7 Probability Density Generators…

…entropy and perfect graphs and fractional chromatic number of a graph. Chapter 4 is devoted to minimum entropy colouring of a given graph and its connection to the graph entropy. G. Simonyi in [36] showed that the maximum of the graph entropy of…

…a given graph over the probability density of its vertex set is equal to its fractional chromatic number. We call a graph is symmetric with respect to graph entropy if the uniform density maximizes its entropy. We show that vertex transitive graphs…

…with its fractional chromatic number in more detail. Furthermore, we obtain the fractional chromatic number of a vertex transitive graph using its properties along with the Lagrange Multiplier technique in convex optimization. 3.1 Entropy of a Convex…

…F ) we denote by F [Z] the induced subgraph of F on Z. The chromatic number of F is denoted by χ(F ). Let T (n) = {U ⊆ V n : P n (U ) ≥ 1 − }. We define the functional H(G, P ) with…

…33 3.8 Additivity and Sub-additivity . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.9 Perfect Graphs and Graph Entropy . . . . . . . . . . . . . . . . . . . . . . 36 ix 4 Chromatic Entropy 39 4.1 Minimum Entropy Coloring…

…39 4.2 Entropy Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3 Number of Colours and Brooks’ Theorem . . . . . . . . . . . . . . . . . . . 43 4.4 Grundy Colouring and Minimum Entropy Colouring…

…information theoretic functional which is defined on a graph with a probability density on its vertex set. This functional was originally proposed by J. K orner in 1973 to study the minimum number of codewords required for representing an information source…

.