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

CREATORGrzegorz Gutowski, Gaurav Kucheriya
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-10340

Browse the full library · About the Tower of Babel