Enumeration of Subtrees of 4-Cactus Networks

Abstract

For a given network, determining its reliability is of great importance. Network reliability can be categorized into global reliability and local reliability. The number of spanning trees can be used to measure the global reliability under edge failures, while the number of subtrees serves as an indicator of local reliability under both edge and vertex failures. Therefore, the enumeration of subtrees is of significant value in network analysis and design. In this paper, we propose a linear-time algorithm for counting the number of subtrees in 4-cactus networks, based on edge-deletion and vertex-deletion contraction principles. Furthermore, we establish the upper and lower bounds for the number of subtrees in 4-cactus networks and characterize the extremal graphs that achieve these bounds. These results provide valuable insights for evaluating network related indices and enhancing network reliability.