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

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

Research output: Contribution to journalArticleScientificpeer-review

4 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
Publication typeA1 Journal article-refereed


  • Graph entropy
  • Spanning forest
  • Subgraph

Publication forum classification

  • Publication forum level 1

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics


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