Randomly Perturbed Digraphs also have Bounded-Degree Spanning Trees
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.
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}
}
EUVIMED