DMTCS Proceedings, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities

Font Size:  Small  Medium  Large

On the number of decomposable trees

Stephan G. Wagner

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 ∞. It turns out that the ratio of k-decomposable trees increases when k becomes large.

Full Text: PDF

Valid XHTML 1.0 Transitional