DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.21

Hunting for Directed 2-Spiders

Authors: Grzegorz Gutowski and Gaurav Kucheriya

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract

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.

Cite as

Grzegorz Gutowski and Gaurav Kucheriya. Hunting for Directed 2-Spiders. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 21:1-21:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gutowski_et_al:LIPIcs.WG.2026.21,
  author =	{Gutowski, Grzegorz and Kucheriya, Gaurav},
  title =	{{Hunting for Directed 2-Spiders}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{21:1--21:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.21},
  URN =		{urn:nbn:de:0030-drops-261879},
  doi =		{10.4230/LIPIcs.WG.2026.21},
  annote =	{Keywords: Oriented and Directed Graphs, Extremal Graph Theory, Mathematics of Computing, Unavoidable Subgraphs}
}

Search Results

Documents authored by Kucheriya, Gaurav

Hunting for Directed 2-Spiders

Abstract

Cite as

Thanks for your feedback!

Could not send message