2018/02/11 by Éva Czabarka, Audace A. V. Dossou-Olory, Czabarka, Éva +5 · 1 citation
Mathematics · Computer Science · #Graph theory and applications #Advanced Graph Theory Research #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.1802.03817
Imitating a recently introduced invariant of trees, we initiate the study of the inducibility of d-ary trees (rooted trees whose vertex outdegrees are bounded from above by d≥ 2) with a given number of leaves. 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 an existing 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.