k-Ary spanning trees contained in tournaments

Abstract

A rooted tree is called a $k$-ary tree, if all non-leaf vertices have exactly $k$ children, except possibly one non-leaf vertex has at most $k-1$ children. Denote by $h(k)$ the minimum integer such that every tournament of order at least $h(k)$ contains a $k$-ary spanning tree. It is well-known that every tournament contains a Hamiltonian path, which implies that $h(1)=1$. Lu et al. [J. Graph Theory {\bf 30}(1999) 167--176] proved the existence of $h(k)$, and showed that $h(2)=4$ and $h(3)=8$. The exact values of $h(k)$ remain unknown for $k\ge 4$. A result of Erdős on the domination number of tournaments implies $h(k)=\Omega (k\log k)$. In this paper, we prove that $h(4)=10$ and $h(5)\ge 13$.

11 pages, to appear in Discrete Applied Mathematics