On the Unavoidability of Oriented Trees

Description

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 with k leaves is (3 2 n + 3 2 k − 2)-unavoidable and (9 2 n − 5 2 k − 9 2)-unavoidable, and thus (21 8 (n − 1))-unavoidable. Finally, we prove that every oriented tree of order n with k leaves is (n + 144k 2 − 280k + 124)-unavoidable.

Abstract

International audience

Additional details