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$$.

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