Tampere University of Technology

TUTCRIS Research Portal

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

Research output: Contribution to journalArticleScientificpeer-review


Original languageEnglish
Article number124616
JournalApplied Mathematics and Computation
Publication statusPublished - 15 Dec 2019
Publication typeA1 Journal article-refereed


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.


  • Graph entropy, Spanning forest, Subgraph

Publication forum classification

Field of science, Statistics Finland