Graph entropy based on the number of spanning forests of c-cyclic graphs

Pengfei Wan, Jianhua Tu, Matthias Dehmer, Shenggui Zhang, F. Emmert-Streib

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


Graph entropies have been introduced to quantitatively measure the structural information content of graphs and networks; they have plenty of applications in various fields. Utilizing the number of subgraphs to establish measures for determining the complexity of molecular graphs are also prevalent in the study of mathematical chemistry. In this paper, we develop a new graph entropy measure that is based on the number of spanning forests. We prove explicit expressions for the entropy for trees, unicyclic and bicyclic graphs, and show that the cycle graph Cn attains the maximal value of the entropy for unicyclic graphs with order n and large cycle lengths. Based on generating numerical results, we conjecture extremal unicyclic graphs with respect to the entropy as well as we compare the values of our entropy for c-cyclic graphs, and generate graphs of bicyclic graphs and tricyclic graphs with 6 vertices for performing further research.

Original languageEnglish
Article number124616
JournalApplied Mathematics and Computation
Publication statusPublished - 15 Dec 2019


  • Graph entropy
  • Spanning forest
  • Subgraph


Dive into the research topics of 'Graph entropy based on the number of spanning forests of c-cyclic graphs'. Together they form a unique fingerprint.

Cite this