Asymptotic enumeration of rooted binary unlabeled galled treeswith a fixed number of galls

Abstract

Galled trees appear in problems concerning admixture, horizontal gene transfer, hybridization, and recombination. Building on a recursive enumerative construction, we study the asymptotic behavior of the number of rooted binary unlabeled (normal) galled trees as the number of leaves n increases maintaining a fixed number of galls g. We find that the exponential growth with n of the number of rooted binary unlabeled normal galled trees with g galls has the same value irrespective of the value of g 0. The subexponential growth, however, depends on g; it follows cgn2g-3/2, where cg is a constant dependent on g. Although for each g, the exponential growth is approximately 2.4833n summing across all g, the exponential growth is instead approximated by the much larger 4.8230n