Please use this identifier to cite or link to this item: https://doi.org/10.15480/882.3578
DC FieldValueLanguage
dc.contributor.authorHahn-Klimroth, Max-
dc.contributor.authorMaesaka, Giulia Satiko-
dc.contributor.authorMogge, Yannick-
dc.contributor.authorMohr, Samuel-
dc.contributor.authorParczyk, Olaf-
dc.date.accessioned2021-06-02T07:50:04Z-
dc.date.available2021-06-02T07:50:04Z-
dc.date.issued2021-05-21-
dc.identifier.citationElectronic Journal of Combinatorics 28 (2): #P2.26 (2021)de_DE
dc.identifier.issn1077-8926de_DE
dc.identifier.urihttp://hdl.handle.net/11420/9656-
dc.description.abstractIn 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). α α αen
dc.language.isoende_DE
dc.publisherEMIS ELibEMSde_DE
dc.relation.ispartofThe electronic journal of combinatoricsde_DE
dc.rights.urihttps://creativecommons.org/licenses/by-nd/4.0/de_DE
dc.subject.ddc510: Mathematikde_DE
dc.titleRandom perturbation of sparse graphsde_DE
dc.typeArticlede_DE
dc.identifier.doi10.15480/882.3578-
dc.type.diniarticle-
dcterms.DCMITypeText-
tuhh.identifier.urnurn:nbn:de:gbv:830-882.0136796-
tuhh.oai.showtruede_DE
tuhh.abstract.englishIn 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). α α αde_DE
tuhh.publisher.doi10.37236/9510-
tuhh.publication.instituteMathematik E-10de_DE
tuhh.identifier.doi10.15480/882.3578-
tuhh.type.opus(wissenschaftlicher) Artikel-
dc.type.driverarticle-
dc.type.casraiJournal Article-
tuhh.container.issue2de_DE
tuhh.container.volume28de_DE
dc.rights.nationallicensefalsede_DE
dc.identifier.scopus2-s2.0-85106001723de_DE
tuhh.container.articlenumber#P2.26de_DE
local.status.inpressfalsede_DE
local.type.versionpublishedVersionde_DE
datacite.resourceTypeJournal Article-
datacite.resourceTypeGeneralText-
item.languageiso639-1en-
item.grantfulltextopen-
item.creatorOrcidHahn-Klimroth, Max-
item.creatorOrcidMaesaka, Giulia Satiko-
item.creatorOrcidMogge, Yannick-
item.creatorOrcidMohr, Samuel-
item.creatorOrcidParczyk, Olaf-
item.mappedtypeArticle-
item.creatorGNDHahn-Klimroth, Max-
item.creatorGNDMaesaka, Giulia Satiko-
item.creatorGNDMogge, Yannick-
item.creatorGNDMohr, Samuel-
item.creatorGNDParczyk, Olaf-
item.fulltextWith Fulltext-
item.openairetypeArticle-
item.openairecristypehttp://purl.org/coar/resource_type/c_6501-
item.cerifentitytypePublications-
crisitem.author.deptMathematik E-10-
crisitem.author.orcid0000-0003-4239-9112-
crisitem.author.orcid0000-0002-9947-821X-
crisitem.author.orcid0000-0001-6419-8560-
crisitem.author.parentorgStudiendekanat Elektrotechnik, Informatik und Mathematik-
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 simple item record

Page view(s)

103
Last Week
0
Last month
3
checked on Aug 8, 2022

Download(s)

41
checked on Aug 8, 2022

SCOPUSTM   
Citations

1
Last Week
0
Last month
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 Creative Commons