Random perturbation of sparse graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F21%3A00125244" target="_blank" >RIV/00216224:14330/21:00125244 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.37236/9510" target="_blank" >https://doi.org/10.37236/9510</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.37236/9510" target="_blank" >10.37236/9510</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Random perturbation of sparse graphs

Popis výsledku v původním jazyce

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 ε &gt; 0 and α : N ↦ ( 0 , 1 ) we show that a.a.s. G α ∪ G ( n , β / n ) is Hamiltonian, where β = − ( 6 + ε ) log ( α ) . If α &gt; 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 ) .

Název v anglickém jazyce

Random perturbation of sparse graphs

Popis výsledku anglicky

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 ε &gt; 0 and α : N ↦ ( 0 , 1 ) we show that a.a.s. G α ∪ G ( n , β / n ) is Hamiltonian, where β = − ( 6 + ε ) log ( α ) . If α &gt; 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 ) .

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Electronic Journal of Combinatorics

ISSN

1077-8926

e-ISSN

—

Svazek periodika

28

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

12

Strana od-do

1-12

Kód UT WoS článku

000762018300001

EID výsledku v databázi Scopus

2-s2.0-85106001723