Enumeration of subtrees of planar two-tree networks

摘要

The number of subtrees, also referred to as the subtrees index, is a key parameter to measure graph structures such as networks. In this paper, we investigate the number of subtrees of planar two-tree networks. By “adding a virtual edge” and “edge orientation”, we present a linear time algorithm for computing the number of subtrees of planar two-tree networks, as well as a family of planar two-connected networks. As applications, we provide the formulae for the number of subtrees of the famous small-world Farey network and GDURT network. We also discuss the relationship between the spanning subtree number and the subtree number of these networks.