On the unavoidability of oriented trees

12/12/2018

∙

by   Francois Dross, et al.

∙

0

∙

share

A digraph is n-unavoidable if it is contained in every tournament of order n. We first prove that every arborescence of order n with k leaves is (n+k-1)-unavoidable. We then prove that every oriented tree of order n (n≥ 2) with k leaves is (3/2n+3/2k -2)-unavoidable and (9/2n -5/2k -9/2)-unavoidable, and thus (21/8 n- 47/16)-unavoidable. Finally, we prove that every oriented tree of order n with k leaves is (n+ 144k^2 - 280k + 124)-unavoidable.