×

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
PDF BibTeX XML Cite
Full Text: DOI