Enumeration of subtrees and BC-subtrees with maximum degree no more than k in trees

The subtrees and BC-subtrees (subtrees where any two leaves are at even distance apart) have been intensively studied in recent years. Such structures, under special constraints on degrees, have a wide range of applications in many fields. By way of an approach based on generating functions, we present novel recursive algorithms for enumerating various subtrees and BC-subtrees of maximum degree ≤k in trees. The algorithms are explained through detailed examples. We also briefly discuss, in trees, the densities of subtrees (resp. BC-subtrees) with maximum degree ≤k among all subtrees (resp. BC-subtrees). For a tree of order n, the novelly proposed algorithms have multiple advantages. (1) Novel (k+2) (resp. (2k+3)) variable generating functions were introduced to construct the algorithms. (2) The proposed algorithms solved the fast enumerating problem of subtree (resp. BC-subtrees) with maximum degree constraint, and also make the subtree (resp. BC-subtrees) enumerating algorithms proposed by Yan and Yeh [1] (resp. Yang et al. [2]) a special case of ours with k=n−1. (3) The time complexity of our algorithm for subtree (resp. BC-subtrees) is O(kn) (resp. O(kn²)), which is much faster than the O(n²) (resp. O(kn³)) time method based on algorithm proposed in [1] (resp. [2]).