On graph entropy measures based on the number of independent sets and matchings

Pengfei Wan, Xinzhuang Chen, Jianhua Tu, Matthias Dehmer, Shenggui Zhang, Frank Emmert-Streib

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)491-504
Number of pages14
JournalInformation Sciences
Volume516
DOIs
Publication statusPublished - Apr 2020

Keywords

  • Graph entropy measures
  • Independent set
  • Matching
  • Quantitative graph theory
  • Subgraph

Fingerprint Dive into the research topics of 'On graph entropy measures based on the number of independent sets and matchings'. Together they form a unique fingerprint.

Cite this