Entropy and Enumeration of Subtrees in a Cactus Network
For a given network, the number of spanning trees is a key parameter to measure its reliability in edge failure cases, while the number of subtrees is a key parameter to measure its reliability in both vertex and edge failures cases. Zhang et al. investigated the entropy of spanning trees, spanning...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Frontiers Media S.A.
2020-10-01
|
| Series: | Frontiers in Physics |
| Subjects: | |
| Online Access: | https://www.frontiersin.org/article/10.3389/fphy.2020.575648/full |
| _version_ | 1818336216253202432 |
|---|---|
| author | Lixin Dong Haixing Zhao Hong-Jian Lai |
| author_facet | Lixin Dong Haixing Zhao Hong-Jian Lai |
| author_sort | Lixin Dong |
| collection | DOAJ |
| description | For a given network, the number of spanning trees is a key parameter to measure its reliability in edge failure cases, while the number of subtrees is a key parameter to measure its reliability in both vertex and edge failures cases. Zhang et al. investigated the entropy of spanning trees, spanning forests and connected spanning subgraphs of Koch networks. In this paper, we extend Koch networks to 3–cactus networks, and study the entropy of subtrees of 3–cactus networks. We present a linear algorithm to count the number of subtrees in a 3–cactus network, determine the upper and lower bounds of the entropy of subtrees of these networks and characterize those attaining the extremal values. As an application, a linear algorithm is developed to count the number of subtrees in Koch networks, with complexity O(g), where g is the number of iterations. Finally, we determine the entropy of subtrees of Koch networks. |
| first_indexed | 2024-12-13T14:35:48Z |
| format | Article |
| id | doaj.art-04b19b4513254ccd9663a69f5721bec6 |
| institution | Directory Open Access Journal |
| issn | 2296-424X |
| language | English |
| last_indexed | 2024-12-13T14:35:48Z |
| publishDate | 2020-10-01 |
| publisher | Frontiers Media S.A. |
| record_format | Article |
| series | Frontiers in Physics |
| spelling | doaj.art-04b19b4513254ccd9663a69f5721bec62022-12-21T23:41:43ZengFrontiers Media S.A.Frontiers in Physics2296-424X2020-10-01810.3389/fphy.2020.575648575648Entropy and Enumeration of Subtrees in a Cactus NetworkLixin Dong0Haixing Zhao1Hong-Jian Lai2School of Computer, Qinghai Normal University, Xining, ChinaSchool of Computer, Qinghai Normal University, Xining, ChinaDepartment of Mathematics, West Virginia University, Morgantown, WV, United StatesFor a given network, the number of spanning trees is a key parameter to measure its reliability in edge failure cases, while the number of subtrees is a key parameter to measure its reliability in both vertex and edge failures cases. Zhang et al. investigated the entropy of spanning trees, spanning forests and connected spanning subgraphs of Koch networks. In this paper, we extend Koch networks to 3–cactus networks, and study the entropy of subtrees of 3–cactus networks. We present a linear algorithm to count the number of subtrees in a 3–cactus network, determine the upper and lower bounds of the entropy of subtrees of these networks and characterize those attaining the extremal values. As an application, a linear algorithm is developed to count the number of subtrees in Koch networks, with complexity O(g), where g is the number of iterations. Finally, we determine the entropy of subtrees of Koch networks.https://www.frontiersin.org/article/10.3389/fphy.2020.575648/fullcactus networksKoch networksthe number of subtreesentropy of subtreesreliability |
| spellingShingle | Lixin Dong Haixing Zhao Hong-Jian Lai Entropy and Enumeration of Subtrees in a Cactus Network Frontiers in Physics cactus networks Koch networks the number of subtrees entropy of subtrees reliability |
| title | Entropy and Enumeration of Subtrees in a Cactus Network |
| title_full | Entropy and Enumeration of Subtrees in a Cactus Network |
| title_fullStr | Entropy and Enumeration of Subtrees in a Cactus Network |
| title_full_unstemmed | Entropy and Enumeration of Subtrees in a Cactus Network |
| title_short | Entropy and Enumeration of Subtrees in a Cactus Network |
| title_sort | entropy and enumeration of subtrees in a cactus network |
| topic | cactus networks Koch networks the number of subtrees entropy of subtrees reliability |
| url | https://www.frontiersin.org/article/10.3389/fphy.2020.575648/full |
| work_keys_str_mv | AT lixindong entropyandenumerationofsubtreesinacactusnetwork AT haixingzhao entropyandenumerationofsubtreesinacactusnetwork AT hongjianlai entropyandenumerationofsubtreesinacactusnetwork |