Skip to Main content Skip to Navigation
Conference papers

On the number of decomposable trees

Abstract : 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 so-called 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.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Monday, August 17, 2015 - 2:24:17 PM
Last modification on : Thursday, May 11, 2017 - 1:02:51 AM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:08:37 PM


Publisher files allowed on an open archive




Stephan G. Wagner. On the number of decomposable trees. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. pp.301-308, ⟨10.46298/dmtcs.3497⟩. ⟨hal-01184701⟩



Record views


Files downloads