Stephan G. Wagner

On the number of decomposable trees
dmtcs:3497 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2006,
DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities

https://doi.org/10.46298/dmtcs.3497
On the number of decomposable trees
Authors: Stephan G. Wagner ^{1}
NULL
Stephan G. Wagner
1 Institut für Analysis und Computational Number Theory
A tree is called $k$decomposable if it has a spanning forest whose components are all of size $k$. Analogously, a tree is called $T$decomposable for a fixed tree $T$ if it has a spanning forest whose components are all isomorphic to $T$. In this paper, we use a generating functions approach to derive exact and asymptotic results on the number of $k$decomposable and $T$decomposable trees from a socalled simply generated family of trees  we find that there is a surprisingly simple functional equation for the counting series of $k$decomposable trees. In particular, we will study the limit case when $k$ goes to $\infty$. It turns out that the ratio of $k$decomposable trees increases when $k$ becomes large.