Trees in tournaments (Q5957701): Difference between revisions

A digraph is said to be \(n\)-unavoidable if ever tournament of order \(n\) contains it as a subgraph. Let \(f(n)\) be the smallest integer such that every oriented tree is \(f(n)\)-unavoidable. Let \(g(k)\) be the smallest integer such that every oriented tree of order \(n\) with \(k\) leaves is \([n+ g(k)]\)-unavoidable. In this paper, it is shown that if a tree is the union of disjoint paths emerging from a common origin, then such a tree of order \(n\) of \(k\) paths is \([n+{3\over 2}(k^2- 3k)+ 5]\)-unavoidable. In particular, a tree with three leaves is \((n+5)\)-unavoidable or \(g(3)\leq 5\). By studying trees with few leaves, it is then shown that \(f(n)\leq {38\over 5}n- 6\).