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

https://hal.inria.fr/hal-01184701
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

File

dmAG0121.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

37

Files downloads

353