Thumbnail
Access Restriction
Open

Author Wagner, Stephan G.
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword K-decomposable Tree ♦ Decomposable Tree ♦ Fixed Tree ♦ Simple Functional Equation ♦ K-decomposable Tree Increase ♦ Limit Case ♦ Counting Series ♦ Generating Function ♦ Asymptotic Result ♦ T-decomposable Tree
Description 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.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2006-01-01
Publisher Institution In Proceedings of the Fourth Colloquium on Mathematics and Computer Science (Nancy 2006