Hunting for Directed 2-Spiders

Abstract

Hons, Klimošová, Kucheriya, Mikšaník, Tkadlec, and Tyomkyn proved that, for every integer $\ell \ge 1$, every directed graph with minimum out-degree at least $3.23\cdot \ell$ contains a $(2,\ell )$-spider (a $1$-subdivision of the in-star with $\ell$ leaves) as a subgraph. They also conjectured that the bound on the minimum out-degree can be further improved to $2\ell$. In this note, we confirm their conjecture by showing that every directed graph with minimum out-degree at least $2\ell$ contains a $(2,\ell )$-spider as a subgraph. This result is best possible, as the complete directed graph with $2\ell$ vertices does not contain a $(2,\ell )$-spider.

Fixed an error in the grant information