Inducibility of d-ary trees
| dc.contributor.author | Czabarka, Eva | en_ZA |
| dc.contributor.author | Dossou-Olory, Audace A. V. | en_ZA |
| dc.contributor.author | Szekely, Laszlo A. | en_ZA |
| dc.contributor.author | Wagner, Stephan | en_ZA |
| dc.date.accessioned | 2022-06-30T15:00:49Z | |
| dc.date.available | 2022-06-30T15:00:49Z | |
| dc.date.issued | 2020 | |
| dc.description | CITATION: Czabarka, E. et al. 2020. Inducibility of d-ary trees. Discrete Mathematics, 343(2). doi:10.1016/j.disc.2019.111671. | |
| dc.description | The original publication is available at https://www.sciencedirect.com/journal/discrete-mathematics | |
| dc.description.abstract | Imitating the binary inducibility, a recently introduced invariant of binary trees (Cz- abarka et al., 2017), we initiate the study of the inducibility of d-ary trees (rooted trees whose vertex outdegrees are bounded from above by d ≥ 2). We determine the exact inducibility for stars and binary caterpillars. For T in the family of strictly d-ary trees (every vertex has 0 or d children), we prove that the difference between the maximum density of a d-ary tree D in T and the inducibility of D is of order O(|T |−1/2) compared to the general case where it is shown that the difference is O(|T |−1) which, in particular, responds positively to a conjecture on the inducibility in binary trees. We also discover that the inducibility of a binary tree in d-ary trees is independent of d. Furthermore, we establish a general lower bound on the inducibility and also provide a bound for some special trees. Moreover, we find that the maximum inducibility is attained for binary caterpillars for every d. | en_ZA |
| dc.description.uri | https://www.sciencedirect.com/science/article/pii/S0012365X19303498 | |
| dc.description.version | Publishers version | |
| dc.format.extent | 15 pages | |
| dc.identifier.citation | Czabarka, E. et al. 2020. Inducibility of d-ary trees. Discrete Mathematics, 343(2). doi:10.1016/j.disc.2019.111671. | |
| dc.identifier.issn | 0012-365X (print) | |
| dc.identifier.other | doi:10.1016/j.disc.2019.111671 | |
| dc.identifier.uri | http://hdl.handle.net/10019.1/125443 | |
| dc.language.iso | en_ZA | en_ZA |
| dc.publisher | Elsevier | |
| dc.rights.holder | Elsevier | |
| dc.subject | D-ary trees | en_ZA |
| dc.subject | Leaf-induced subtrees | en_ZA |
| dc.subject | Inducibility | en_ZA |
| dc.subject | Maximum density | en_ZA |
| dc.subject | Stars | en_ZA |
| dc.subject | Caterpillars | en_ZA |
| dc.subject | Phylogenetics | en_ZA |
| dc.subject | Rooted trees -- Mathematical model | en_ZA |
| dc.title | Inducibility of d-ary trees | en_ZA |
| dc.type | Article | en_ZA |