Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for subject:(Vertex packing polytope). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters

1. Changiz Rezaei, Seyed Saeed. Entropy and Graphs.

Degree: 2014, University of Waterloo

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ö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 FG(P)} defined on the set of all the probability distributions on its vertex set if the distribution P^* maximizing FG(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

…entropy in terms of the vertex packing polytope of the graph. They also gave another… …entropy of a graph. Let V P (G) be the vertex packing polytope of a given graph G… …x29; denote the vertex packing polytope of G. The entropy of G with respect to P is then… …packing polytope V P (G) of a graph G, which is the convex hull of the characteristic… …which is defined on a graph with a probability density on its vertex set. This functional was… 

Page 1 Page 2 Page 3 Page 4 Page 5 Page 6 Page 7

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Changiz Rezaei, S. S. (2014). Entropy and Graphs. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/8173

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th Edition):

Changiz Rezaei, Seyed Saeed. “Entropy and Graphs.” 2014. Thesis, University of Waterloo. Accessed August 04, 2020. http://hdl.handle.net/10012/8173.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th Edition):

Changiz Rezaei, Seyed Saeed. “Entropy and Graphs.” 2014. Web. 04 Aug 2020.

Vancouver:

Changiz Rezaei SS. Entropy and Graphs. [Internet] [Thesis]. University of Waterloo; 2014. [cited 2020 Aug 04]. Available from: http://hdl.handle.net/10012/8173.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Changiz Rezaei SS. Entropy and Graphs. [Thesis]. University of Waterloo; 2014. Available from: http://hdl.handle.net/10012/8173

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

.