On the number of decomposable trees
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 der...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2006-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3497/pdf |
| _version_ | 1827324129336885248 |
|---|---|
| author | Stephan G. Wagner |
| author_facet | Stephan G. Wagner |
| author_sort | Stephan G. Wagner |
| collection | DOAJ |
| 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 $\infty$. It turns out that the ratio of $k$-decomposable trees increases when $k$ becomes large. |
| first_indexed | 2024-04-25T02:03:49Z |
| format | Article |
| id | doaj.art-403ade582e454b4dabb776d2f1b101f0 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:03:49Z |
| publishDate | 2006-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-403ade582e454b4dabb776d2f1b101f02024-03-07T14:34:36ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502006-01-01DMTCS Proceedings vol. AG,...Proceedings10.46298/dmtcs.34973497On the number of decomposable treesStephan G. Wagner0Institut für Analysis und Computational Number TheoryA 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.https://dmtcs.episciences.org/3497/pdfdecomposable treesimply generated family of treesgenerating functionsasymptotic analysis[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds][info.info-dm] computer science [cs]/discrete mathematics [cs.dm][math.math-co] mathematics [math]/combinatorics [math.co] |
| spellingShingle | Stephan G. Wagner On the number of decomposable trees Discrete Mathematics & Theoretical Computer Science decomposable tree simply generated family of trees generating functions asymptotic analysis [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] |
| title | On the number of decomposable trees |
| title_full | On the number of decomposable trees |
| title_fullStr | On the number of decomposable trees |
| title_full_unstemmed | On the number of decomposable trees |
| title_short | On the number of decomposable trees |
| title_sort | on the number of decomposable trees |
| topic | decomposable tree simply generated family of trees generating functions asymptotic analysis [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] |
| url | https://dmtcs.episciences.org/3497/pdf |
| work_keys_str_mv | AT stephangwagner onthenumberofdecomposabletrees |