2026-07-21T15:08:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26187 2026-07-02T07:14:09Z ddc:004 open_access

Hunting for Directed 2-Spiders Gutowski, Grzegorz Kucheriya, Gaurav Oriented and Directed Graphs Extremal Graph Theory Mathematics of Computing Unavoidable Subgraphs Hons, Klimošová, Mikšaník, Tkadlec, Tyomkyn and the second author proved that, for every integer 𝓁 ≥ 1, every directed graph with minimum out-degree at least 3.23 ⋅ 𝓁 contains a (2,𝓁)-spider (a 1-subdivision of the in-star with 𝓁 leaves) as a subgraph. Hons et al. also conjectured that the bound on the minimum out-degree can be further improved to 2 𝓁. In this note, we confirm this conjecture by showing that every directed graph with minimum out-degree at least 2𝓁 contains a (2, 𝓁)-spider as a subgraph. This result is best possible, as the complete directed graph with 2𝓁 vertices does not contain a (2,𝓁)-spider. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Grzegorz Gutowski and Gaurav Kucheriya 2026 Is Part Of LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WG.2026.21 urn:nbn:de:0030-drops-261879 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.21 eng https://creativecommons.org/licenses/by/4.0/legalcode