The Evaluation of the Number and the Entropy of Spanning Trees on Generalized Small‐World Networks

Raihana Mokhlissi, Dounia Lotfi, Joyati Debnath, Mohamed El Marraki and Noussaima EL Khattabi

Journal of Applied Mathematics, 2018, vol. 2018, issue 1

Abstract: Spanning trees have been widely investigated in many aspects of mathematics: theoretical computer science, combinatorics, so on. An important issue is to compute the number of these spanning trees. This number remains a challenge, particularly for large and complex networks. As a model of complex networks, we study two families of generalized small‐world networks, namely, the Small‐World Exponential and the Koch networks, by changing the size and the dimension of the cyclic subgraphs. We introduce their construction and their structural properties which are built in an iterative way. We propose a decomposition method for counting their number of spanning trees and we obtain the exact formulas, which are then verified by numerical simulations. From this number, we find their spanning tree entropy, which is lower than that of the other networks having the same average degree. This entropy allows quantifying the robustness of the networks and characterizing their structures.

Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1155/2018/1017308

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:jnljam:v:2018:y:2018:i:1:n:1017308

Access Statistics for this article

More articles in Journal of Applied Mathematics from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().