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 <>
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

  • HAL Id : hal-01184701, version 1

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. ⟨hal-01184701⟩

Share

Metrics

Record views

73

Files downloads

541