EUVIMEDEUVIMED entdecken
Crossref

Hitting Cycles through Prescribed Vertices or Edges

Nathan Bowler, Ebrahim Ghorbani, Florian Gut, Raphael W. Jacobs, Florian Reich

SIAM Journal on Discrete Mathematics · 30.09.2026 · 40 (3) · 988-999

DOI: 10.1137/24m1716604 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 07.07.2026. Verfasst von Nathan Bowler und 4 weiteren Autor:innen. Die Arbeit nennt 18 Literaturangaben. Gefördert von: Alexander von Humboldt-Stiftung, Cusanuswerk - Bischofliche Studienforderung, Studienstiftung des Deutschen Volkes.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We prove that for every set [Formula: see text] of vertices of a directed graph [Formula: see text], the maximum number of vertices in [Formula: see text] contained in a collection of vertex-disjoint cycles in [Formula: see text] is at least the minimum size of a set of vertices that hits all cycles containing a vertex of [Formula: see text]. As a consequence, the directed tree-width of a directed graph is linearly bounded in its cycle-width, which improves the previously known quadratic upper bound. We further show that the corresponding statement in bidirected graphs is true and that its edge-variant holds in both undirected and directed graphs, but fails in bidirected graphs. The vertex-version in undirected graphs remains an open problem.

Förderung

  • Alexander von Humboldt-Stiftung
  • Cusanuswerk - Bischofliche Studienforderung
  • Studienstiftung des Deutschen Volkes

Zitieren

APA

Bowler, N., Ghorbani, E., Gut, F., Jacobs, R. W., & Reich, F. (2026). Hitting Cycles through Prescribed Vertices or Edges. SIAM Journal on Discrete Mathematics, 40(3), 988-999. https://doi.org/10.1137/24m1716604

Vancouver

Bowler N, Ghorbani E, Gut F, Jacobs RW, Reich F. Hitting Cycles through Prescribed Vertices or Edges. SIAM Journal on Discrete Mathematics. 2026;40(3):988-999. doi:10.1137/24m1716604

BibTeX
@article{Bowler2026,
  author = {Bowler, Nathan and Ghorbani, Ebrahim and Gut, Florian and Jacobs, Raphael W. and Reich, Florian},
  title = {Hitting Cycles through Prescribed Vertices or Edges},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2026},
  volume = {40},
  number = {3},
  pages = {988--999},
  doi = {10.1137/24m1716604}
}
Kostenlos starten →