EUVIMEDEUVIMED entdecken
Crossref

Antidirected subgraphs of oriented graphs

Maya Stein, Camila Zárate-Guerén

Combinatorics, Probability and Computing · 2024-07 · 33 (4) · 446-466

DOI: 10.1017/s0963548324000038 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Combinatorics, Probability and Computing, online erschienen am 06.03.2024. Verfasst von Maya Stein und 1 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 32 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We show that for every $\eta \gt 0$ every sufficiently large $n$ -vertex oriented graph $D$ of minimum semidegree exceeding $(1+\eta )\frac k2$ contains every balanced antidirected tree with $k$ edges and bounded maximum degree, if $k\ge \eta n$ . In particular, this asymptotically confirms a conjecture of the first author for long antidirected paths and dense digraphs. Further, we show that in the same setting, $D$ contains every $k$ -edge antidirected subdivision of a sufficiently small complete graph, if the paths of the subdivision that have length $1$ or $2$ span a forest. As a special case, we can find all antidirected cycles of length at most $k$ . Finally, we address a conjecture of Addario-Berry, Havet, Linhares Sales, Reed, and Thomassé for antidirected trees in digraphs. We show that this conjecture is asymptotically true in $n$ -vertex oriented graphs for all balanced antidirected trees of bounded maximum degree and of size linear in $n$ .

Zitieren

APA

Stein, M., & Zárate-Guerén, C. (2024). Antidirected subgraphs of oriented graphs. Combinatorics, Probability and Computing, 33(4), 446-466. https://doi.org/10.1017/s0963548324000038

Vancouver

Stein M, Zárate-Guerén C. Antidirected subgraphs of oriented graphs. Combinatorics, Probability and Computing. 2024;33(4):446-466. doi:10.1017/s0963548324000038

BibTeX
@article{Stein2024,
  author = {Stein, Maya and Zárate-Guerén, Camila},
  title = {Antidirected subgraphs of oriented graphs},
  journal = {Combinatorics, Probability and Computing},
  year = {2024},
  volume = {33},
  number = {4},
  pages = {446--466},
  doi = {10.1017/s0963548324000038}
}
Kostenlos starten →