EUVIMEDEUVIMED entdecken
Crossref

Antidirected Trees in Dense Digraphs

Maya Stein, Ana Trujillo-Negrete

SIAM Journal on Discrete Mathematics · 30.06.2025 · 39 (2) · 698-727

DOI: 10.1137/24m165497x ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 17.04.2025. Verfasst von Maya Stein und 1 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 14 Literaturangaben. Gefördert von: Fondo Nacional de Desarrollo Científico y Tecnológico, ANID, H2020 Marie Skłodowska-Curie Actions.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We show that if [Formula: see text] is an [Formula: see text]-vertex digraph with more than [Formula: see text] arcs that does not contain any of three forbidden digraphs, then [Formula: see text] contains every antidirected tree on [Formula: see text] arcs. The forbidden digraphs are those orientations of [Formula: see text] where each of the vertices in the class of size two has either out-degree 0 or in-degree 0. This proves a conjecture of Addario-Berry et al. for a broad class of digraphs, and generalizes a result for [Formula: see text]-free graphs by Balasubramanian and Dobson. We also show that every digraph [Formula: see text] on [Formula: see text] vertices with more than [Formula: see text] arcs contains every antidirected [Formula: see text]-arc caterpillar, thus solving the above conjecture for caterpillars. This generalizes a result of Perles.

Förderung

  • Fondo Nacional de Desarrollo Científico y Tecnológico
  • ANID
  • H2020 Marie Skłodowska-Curie Actions

Zitieren

APA

Stein, M., & Trujillo-Negrete, A. (2025). Antidirected Trees in Dense Digraphs. SIAM Journal on Discrete Mathematics, 39(2), 698-727. https://doi.org/10.1137/24m165497x

Vancouver

Stein M, Trujillo-Negrete A. Antidirected Trees in Dense Digraphs. SIAM Journal on Discrete Mathematics. 2025;39(2):698-727. doi:10.1137/24m165497x

BibTeX
@article{Stein2025,
  author = {Stein, Maya and Trujillo-Negrete, Ana},
  title = {Antidirected Trees in Dense Digraphs},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2025},
  volume = {39},
  number = {2},
  pages = {698--727},
  doi = {10.1137/24m165497x}
}
Kostenlos starten →