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

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.