IIIT Hyderabad Publications |
|||||||||
|
Novel Shannon Graph Entropy, Capacity: Spectral Graph TheoryAuthors: Garimella Ramamurthy Date: 2015-10-15 Report no: IIIT/TR/2015/61 AbstractIn this research paper, an interesting probability mass function is associated with the vertices of graph. One among the various possible entropies ( Shannon, Renyii, Tsallis etc ) is associated with such a probability mass function. Specifically Shannon entropy is utilized to define a novel graph entropy. Characterization of minimum and maximum Shannon entropy graphs is discussed. By associating a symmetric stochastic matrix with the graph, novel Shannon Capacity of a graph is defined. Several interesting results in spectral graph theory of structured graphs are reported. New results related to sparsest and densest cut computation are reported ( without invoking Cheeger’s inequality ). Full report: pdf Centre for Security, Theory and Algorithms |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |