EUVIMEDEUVIMED entdecken
Crossref

Randomly Perturbed Digraphs also have Bounded-Degree Spanning Trees

Patryk Morawski, Kalina Petrova

The Electronic Journal of Combinatorics · 08.05.2026 · 33 (2)

DOI: 10.37236/13316 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 08.05.2026. Verfasst von Patryk Morawski und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We show that a randomly perturbed digraph, where we start with a dense digraph $D_{\alpha}$ and add a small number of random edges to it, will typically contain a fixed orientation of a bounded-degree spanning tree. This answers a question posed by Araujo, Balogh, Krueger, Piga and Treglown and generalizes the corresponding result for randomly perturbed graphs by Krivelevich, Kwan and Sudakov. More specifically, we prove that there exists a constant $c = c(\alpha, \Delta)$ such that if $T$ is an oriented tree with maximum degree $\Delta$ and $D_\alpha$ is an $n$-vertex digraph with minimum semidegree $\alpha n$, then the graph obtained by adding $cn$ uniformly random edges to $D_\alpha$ will contain $T$ with high probability.

Zitieren

APA

Morawski, P., & Petrova, K. (2026). Randomly Perturbed Digraphs also have Bounded-Degree Spanning Trees. The Electronic Journal of Combinatorics, 33(2). https://doi.org/10.37236/13316

Vancouver

Morawski P, Petrova K. Randomly Perturbed Digraphs also have Bounded-Degree Spanning Trees. The Electronic Journal of Combinatorics. 2026;33(2). doi:10.37236/13316

BibTeX
@article{Morawski2026,
  author = {Morawski, Patryk and Petrova, Kalina},
  title = {Randomly Perturbed Digraphs also have Bounded-Degree Spanning Trees},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  volume = {33},
  number = {2},
  doi = {10.37236/13316}
}
Kostenlos starten →