On the Unavoidability of Oriented Trees

François Dross 1 Frédéric Havet 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-02350215
Contributor : Frederic Havet <>
Submitted on : Wednesday, November 6, 2019 - 1:02:48 AM
Last modification on : Thursday, November 7, 2019 - 1:30:08 AM

File

ENTCS.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

François Dross, Frédéric Havet. On the Unavoidability of Oriented Trees. Electronic Notes in Theoretical Computer Science, Elsevier, 2019, 346, pp.425-436. ⟨10.1016/j.entcs.2019.08.038⟩. ⟨hal-02350215⟩

Share

Metrics

Record views

23

Files downloads

167