Inducibility of d-ary trees

Czabarka, Eva ; Dossou-Olory, Audace A. V. ; Szekely, Laszlo A. ; Wagner, Stephan (2020)

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

Article

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.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/125443
This item appears in the following collections: