Verlagslink DOI: 10.37236/9510
Titel: Random perturbation of sparse graphs
Sprache: Englisch
Autor/Autorin: Hahn-Klimroth, Max 
Maesaka, Giulia Satiko 
Mogge, Yannick 
Mohr, Samuel 
Parczyk, Olaf 
Erscheinungs­datum: 21-Mai-2021
Verlag: EMIS ELibEMS
Quellenangabe: Electronic Journal of Combinatorics 28 (2): #P2.26 (2021)
Zusammenfassung (englisch): 
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
Zeitschrift: The electronic journal of combinatorics 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Lizenz: CC BY-ND 4.0 (Attribution-NoDerivatives) CC BY-ND 4.0 (Attribution-NoDerivatives)
Enthalten in den Sammlungen:Publications with fulltext

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat
9510-PDF file-36083-1-10-20210511.pdfVerlags-PDF294,06 kBAdobe PDFÖffnen/Anzeigen
Miniaturbild
Zur Langanzeige

Seitenansichten

114
Letzte Woche
0
Letzten Monat
3
checked on 01.10.2022

Download(s)

48
checked on 01.10.2022

SCOPUSTM   
Zitate

1
Letzte Woche
0
Letzten Monat
0
checked on 29.06.2022

Google ScholarTM

Prüfe

Feedback zu diesem Datensatz

Diesen Datensatz zitieren

Export

Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons Creative Commons