2022/06/26 by Audace A. V. Dossou-Olory, Dossou-Olory, Audace A. V., Ignatius Boadi +1
Computer Science · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Theoretical and Computational Physics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2206.14287
openalex publication_date 2022/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A subtree can be induced in a natural way by a subset of leaves of a rooted tree. We study the number of nonisomorphic such subtrees induced by leaves (leaf-induced subtrees) of a rooted tree with no vertex of outdegree 1 (topological tree). We show that only stars and binary caterpillars have the minimum nonisomorphic leaf-induced subtrees among all topological trees with a given number of leaves. We obtain a closed formula and a recursive formula for the families of d-ary caterpillars and complete d-ary trees, respectively. An asymptotic formula is found for complete d-ary trees using polynomial recurrences. We also show that the complete binary tree of height h>1 contains precisely \lfloor 2(1.24602...)2h\rfloor nonisomorphic leaf-induced subtrees.