---
DOAJ_listed: '1'
OA_place: publisher
OA_type: gold
_id: '21884'
abstract:
- lang: eng
  text: "We show that a randomly perturbed digraph, where we start with a dense digraph
    Dα 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(α,Δ) such that if \r\nT is an oriented
    tree with maximum degree Δ and Dα is an n-vertex digraph with minimum semidegree
    αn, then the graph obtained by adding cn uniformly random edges to Dα will contain
    T with high probability."
acknowledgement: "We thank the anonymous referees for many helpful comments on an
  earlier version of this\r\narticle. Kalina Petrova was supported by grant no. CRSII5
  173721 of the Swiss National\r\nScience Foundation, and by the European Union’s
  Horizon 2020 research and innovation\r\nprogramme under the Marie Sk lodowska-Curie
  grant agreement No. 101034413"
article_number: P2.24
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Patryk
  full_name: Morawski, Patryk
  last_name: Morawski
- first_name: Kalina H
  full_name: Petrova, Kalina H
  id: 554ff4e4-f325-11ee-b0c4-a10dbd523381
  last_name: Petrova
citation:
  ama: Morawski P, Petrova KH. Randomly perturbed digraphs also have bounded-degree
    spanning trees. <i>Electronic Journal of Combinatorics</i>. 2026;33(2). doi:<a
    href="https://doi.org/10.37236/13316">10.37236/13316</a>
  apa: Morawski, P., &#38; Petrova, K. H. (2026). Randomly perturbed digraphs also
    have bounded-degree spanning trees. <i>Electronic Journal of Combinatorics</i>.
    Electronic Journal of Combinatorics. <a href="https://doi.org/10.37236/13316">https://doi.org/10.37236/13316</a>
  chicago: Morawski, Patryk, and Kalina H Petrova. “Randomly Perturbed Digraphs Also
    Have Bounded-Degree Spanning Trees.” <i>Electronic Journal of Combinatorics</i>.
    Electronic Journal of Combinatorics, 2026. <a href="https://doi.org/10.37236/13316">https://doi.org/10.37236/13316</a>.
  ieee: P. Morawski and K. H. Petrova, “Randomly perturbed digraphs also have bounded-degree
    spanning trees,” <i>Electronic Journal of Combinatorics</i>, vol. 33, no. 2. Electronic
    Journal of Combinatorics, 2026.
  ista: Morawski P, Petrova KH. 2026. Randomly perturbed digraphs also have bounded-degree
    spanning trees. Electronic Journal of Combinatorics. 33(2), P2.24.
  mla: Morawski, Patryk, and Kalina H. Petrova. “Randomly Perturbed Digraphs Also
    Have Bounded-Degree Spanning Trees.” <i>Electronic Journal of Combinatorics</i>,
    vol. 33, no. 2, P2.24, Electronic Journal of Combinatorics, 2026, doi:<a href="https://doi.org/10.37236/13316">10.37236/13316</a>.
  short: P. Morawski, K.H. Petrova, Electronic Journal of Combinatorics 33 (2026).
corr_author: '1'
date_created: 2026-05-17T22:02:11Z
date_published: 2026-05-08T00:00:00Z
date_updated: 2026-05-18T08:50:18Z
day: '08'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.37236/13316
ec_funded: 1
external_id:
  arxiv:
  - '2306.14648'
file:
- access_level: open_access
  checksum: 9e8402cb2e8870ba7ded9ae7b308201a
  content_type: application/pdf
  creator: dernst
  date_created: 2026-05-18T08:46:26Z
  date_updated: 2026-05-18T08:46:26Z
  file_id: '21893'
  file_name: 2026_ElectrJournCombinatorics_Morawski.pdf
  file_size: 399969
  relation: main_file
  success: 1
file_date_updated: 2026-05-18T08:46:26Z
has_accepted_license: '1'
intvolume: '        33'
issue: '2'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '05'
oa: 1
oa_version: Published Version
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: Electronic Journal of Combinatorics
publication_identifier:
  eissn:
  - 1077-8926
publication_status: published
publisher: Electronic Journal of Combinatorics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Randomly perturbed digraphs also have bounded-degree spanning trees
tmp:
  image: /image/cc_by_nd.png
  legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
  name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
  short: CC BY-ND (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 33
year: '2026'
...