# 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.
Keywords :
Type de document :
Communication dans un congrès
Chassaing, Philippe and others. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp.301-308, 2006, DMTCS Proceedings
Domaine :

Littérature citée [11 références]

https://hal.inria.fr/hal-01184701
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 14:24:17
Dernière modification le : jeudi 11 mai 2017 - 01:02:51
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 12:08:37

### Fichier

dmAG0121.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184701, version 1

### Citation

Stephan G. Wagner. On the number of decomposable trees. Chassaing, Philippe and others. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp.301-308, 2006, DMTCS Proceedings. 〈hal-01184701〉

### Métriques

Consultations de la notice

## 43

Téléchargements de fichiers