pith. sign in

arxiv: 1802.03817 · v1 · pith:22V7FL7Lnew · submitted 2018-02-11 · 🧮 math.CO

Inducibility of d-ary trees

classification 🧮 math.CO
keywords inducibilitytreesbinaryboundcaterpillarsdifferenceeverygeneral
0
0 comments X
read the original abstract

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\geq 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 $\mathcal{O}(|T|^{-1/2})$ compared to the general case where it is shown that the difference is $\mathcal{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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.