2021/02/23 by Matolcsi, Dávid, Nagy, Zoltán Lóránt
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2102.11746
We prove an asymptotic result on the maximum number of k-vertex subtrees in binary trees of given order. This problem turns out to be equivalent to determine the maximum number of k+2-cycles in n-vertex outerplanar graphs, thus we settle the generalized outerplanar Turán number for all cycles. We also determine the exponential growth of the generalized outerplanar Turán number of paths Pk as a function of k which implies the order of magnitude of the generalized outerplanar Turán number of arbitrary trees. The bounds are strongly related to the sequence of Catalan numbers.