Please use this identifier to cite or link to this item:
https://doi.org/10.15480/882.3578
Publisher DOI: | 10.37236/9510 | Title: | Random perturbation of sparse graphs | Language: | English | Authors: | Hahn-Klimroth, Maximilian Grischa Maesaka, Giulia Satiko Mogge, Yannick Mohr, Samuel Parczyk, Olaf |
Issue Date: | 21-May-2021 | Publisher: | EMIS ELibEMS | Source: | Electronic Journal of Combinatorics 28 (2): #P2.26 (2021) | Abstract (english): | 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). α α α |
URI: | http://hdl.handle.net/11420/9656 | DOI: | 10.15480/882.3578 | ISSN: | 1077-8926 | Journal: | The electronic journal of combinatorics | Institute: | Mathematik E-10 | Document Type: | Article | License: | ![]() |
Appears in Collections: | Publications with fulltext |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
9510-PDF file-36083-1-10-20210511.pdf | Verlags-PDF | 294,06 kB | Adobe PDF | View/Open![]() |
Page view(s)
150
Last Week
0
0
Last month
3
3
checked on Jun 9, 2023
Download(s)
85
checked on Jun 9, 2023
SCOPUSTM
Citations
1
Last Week
0
0
Last month
0
0
checked on Jun 29, 2022
Google ScholarTM
Check
Note about this record
Cite this record
Export
This item is licensed under a Creative Commons License