Published August 2019 | Version v1
Journal article

On the Unavoidability of Oriented Trees

Contributors

Other:

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

Identifiers

URL
https://hal.inria.fr/hal-02350215
URN
urn:oai:HAL:hal-02350215v1