On the unavoidability of oriented trees

Publication date 16 September 2021

Abstract: A digraph is {it

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 g e q 2

) with

k

leaves is

(f r a c 32 n + f r a c 32 k - 2)

-unavoidable and

(f r a c 92 n - f r a c 52 k - f r a c 92)

-unavoidable, and thus

(f r a c 218 n - f r a c 4716)

-unavoidable. Finally, we prove that every oriented tree of order

n

with

k

leaves is

(n + 144 k^{2} - 280 k + 124)

-unavoidable.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: On the unavoidability of oriented trees