# zbMATH — the first resource for mathematics

On unavoidability of trees with $$k$$ leaves. (English) Zbl 1022.05014
Let $$g(k)$$ denote the least integer such that every oriented tree with $$n$$ vertices and $$k$$ leaves is contained in every tournament with $$n+g(k)$$ vertices. The author and S. Thomassé have conjectured that $$g(k) \leq k-1$$; see [Discrete Math. 243, 121-134 (2002; Zbl 0995.05037)]. In the present paper the author proves this conjecture for a certain restricted family of oriented trees that he calls constructible.

##### MSC:
 05C05 Trees 05C20 Directed graphs (digraphs), tournaments
##### Keywords:
oriented tree; tournament
Full Text: