zbMATH — the first resource for mathematics

On avoidable and unavoidable trees. (English) Zbl 0858.05034
A directed tree is a rooted tree if there is one vertex (the root) of in-degree \(0\) and all other vertices have in-degree 1. A claw is a rooted tree such that every vertex except the root has out-degree at most 1. A directed graph is called \(n\)-unavoidable if every tournament of order \(n\) contains it as subgraph. A well-known result, given by Redei, can be restated as follows: Every claw of order \(n\) and with cut-degree 1 of the root (that is a Hamilton path) is \(n\)-unavoidable. In a previous paper the author proved that any claw with out-degree of the root at most \(3n/8\) is \(n\)-unavoidable. Define \(\lambda(n)\) to be the largest real number such that every claw with out-degree of the root at most \(\lambda(n)n\) is \(n\)-unavoidable. The paper proves that \(\limsup\lambda(n)\leq 25/52\).

05C05 Trees
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI