Hunting for Directed 2-Spiders
Grzegorz Gutowski, Gaurav Kucheriya · 2026
Read Hunting for Directed 2-Spiders by Grzegorz Gutowski, Gaurav Kucheriya (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-10340.txt.
Description
Directed graphs with high minimum out-degree must contain spider subgraphs, but the exact threshold has been open. A 2026 paper by Grzegorz Gutowski and Gaurav Kucheriya confirms a conjecture of Hons, Klimošová, and co-authors. Any directed graph with minimum out-degree of at least twice the leaf count contains a directed two-spider as a subgraph. An earlier result had required about three and a quarter times the leaf count.
The new bound cannot be beaten, as the complete directed graph on twice as many vertices contains no such spider. The note thus closes the gap between the previous bound and the conjectured optimum, settling the directed spider problem at exactly twice the leaf count.
Catalog record
| CREATOR | Grzegorz Gutowski, Gaurav Kucheriya |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-10340