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, Max 
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)
Journal: The electronic journal of combinatorics 
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
Institute: Mathematik E-10 
Document Type: Article
License: CC BY-ND 4.0 (Attribution-NoDerivatives) CC BY-ND 4.0 (Attribution-NoDerivatives)
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
9510-PDF file-36083-1-10-20210511.pdfVerlags-PDF294,06 kBAdobe PDFView/Open
Thumbnail
Show full item record

Page view(s)

46
Last Week
4
Last month
checked on Jun 23, 2021

Download(s)

10
checked on Jun 23, 2021

Google ScholarTM

Check

Note about this record

Cite this record

Export

This item is licensed under a Creative Commons License Creative Commons