Inducibility of d-ary trees
Date
2020
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
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.
Description
CITATION: Czabarka, E. et al. 2020. Inducibility of d-ary trees. Discrete Mathematics, 343(2). doi:10.1016/j.disc.2019.111671.
The original publication is available at https://www.sciencedirect.com/journal/discrete-mathematics
The original publication is available at https://www.sciencedirect.com/journal/discrete-mathematics
Keywords
D-ary trees, Leaf-induced subtrees, Inducibility, Maximum density, Stars, Caterpillars, Phylogenetics, Rooted trees -- Mathematical model
Citation
Czabarka, E. et al. 2020. Inducibility of d-ary trees. Discrete Mathematics, 343(2). doi:10.1016/j.disc.2019.111671.