TY  - JOUR
A1  - Hahn-Klimroth, Maximilian Grischa
A1  - Maesaka, Giulia Satiko
A1  - Mogge, Yannick
A1  - Mohr, Samuel
A1  - Parczyk, Olaf
T1  - Random perturbation of sparse graphs
T2  - The electronic journal of combinatorics
N2  - In the model of randomly perturbed graphs we consider the union of a deterministic graph G with minimum degree αn and the binomial random graph G(n, p). This model was introduced by Bohman, Frieze, and Martin and for Hamilton cycles their result bridges the gap between Dirac’s theorem and the results by Pósa and Korshunov on the threshold in G(n, p). In this note we extend this result in G ∪G(n, p) to sparser graphs with α = o(1). More precisely, for any ε > 0 and α: N ↦→ (0, 1) we show that a.a.s. G ∪ G(n, β/n) is Hamiltonian, where β = −(6 + ε) log(α). If α > 0 is a fixed constant this gives the aforementioned result by Bohman, Frieze, and Martin and if α = O(1/n) the random part G(n, p) is sufficient for a Hamilton cycle. We also discuss embeddings of bounded degree trees and other spanning structures in this model, which lead to interesting questions on almost spanning embeddings into G(n, p).
Y1  - 2021
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/57684
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-576841
SN  - 1077-8926
N1  - (c) The authors. Released under the CC BY-ND license (International 4.0).
VL  - 28
IS  - issue 2, art. P2.26
SP  - 1
EP  - 12
PB  - EMIS ELibEMS
CY  - [Madralin]
ER  -