Tampere University of Technology

TUTCRIS Research Portal

On Graph Entropy Measures Based on the Number of Independent Sets and Matchings

Research output: Contribution to journalArticleScientificpeer-review


Original languageEnglish
JournalInformation Sciences
Publication statusE-pub ahead of print - 26 Nov 2019
Publication typeA1 Journal article-refereed


In this paper, we consider the graph entropy measures based on the number of independent sets and matchings. The reason to study these measures relates to the fact that the independent set and matching problem is computationally demanding. However, these features can be calculated for smaller networks. In case one can establish efficient estimations, those measures may be also used for larger graphs. So, we establish some upper and lower bounds as well as some information inequalities for these information-theoretic quantities. In order to give further evidence, we also generate numerical results to study these measures such as list the extremal graphs for these entropies. Those results reveal the two entropies possess some new features.


  • Graph entropy measures, Subgraph, Independent set, Matching, Quantitative Graph Theory

Publication forum classification

Field of science, Statistics Finland