Powers of Hamiltonian cycles in randomly augmented Dirac graphs-The complete collection

被引:1
作者
Antoniuk, Sylwia [1 ]
Dudek, Andrzej [2 ]
Rucinski, Andrzej [1 ]
机构
[1] Adam Mickiewicz Univ, Dept Discrete Math, Poznan, Poland
[2] Western Michigan Univ, Dept Math, Kalamazoo, MI 49008 USA
关键词
Dirac graphs; powers of Hamiltonian cycles; random graphs; RANDOM EDGES;
D O I
10.1002/jgt.23001
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We study the powers of Hamiltonian cycles in randomly augmented Dirac graphs, that is, n $n$-vertex graphs G $G$ with minimum degree at least (1/2+& epsilon;)n $(1\unicode{x02215}2+\varepsilon )n$ to which some random edges are added. For any Dirac graph and every integer m & GE;2 $m\ge 2$, we accurately estimate the threshold probability p=p(n) $p=p(n)$ for the event that the random augmentation G?G(n,p) $G\cup G(n,p)$ contains the m $m$-th power of a Hamiltonian cycle.
引用
收藏
页码:811 / 835
页数:25
相关论文
共 9 条
[1]   High powers of Hamiltonian cycles in randomly augmented graphs [J].
Antoniuk, Sylwia ;
Dudek, Andrzej ;
Reiher, Christian ;
Rucinski, Andrzej ;
Schacht, Mathias .
JOURNAL OF GRAPH THEORY, 2021, 98 (02) :255-284
[2]   How many random edges make a dense graph hamiltonian? [J].
Bohman, T ;
Frieze, A ;
Martin, R .
RANDOM STRUCTURES & ALGORITHMS, 2003, 22 (01) :33-42
[3]  
Bottcher J., 2022, ARXIV
[4]  
Dirac G.A., 1952, P LONDON MATH SOC 3, Vs3-2, P69, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]
[5]   Powers of Hamiltonian cycles in randomly augmented graphs [J].
Dudek, Andrzej ;
Reiher, Christian ;
Rucinski, Andrzej ;
Schacht, Mathias .
RANDOM STRUCTURES & ALGORITHMS, 2020, 56 (01) :122-141
[6]  
Komlos J, 1996, RANDOM STRUCT ALGOR, V9, P193, DOI 10.1002/(SICI)1098-2418(199608/09)9:1/2<193::AID-RSA12>3.0.CO
[7]  
2-P
[8]  
Komlos J., 1998, Ann. Comb., V2, P43
[9]   SPRINKLING A FEW RANDOM EDGES DOUBLES THE POWER [J].
Nenadov, Rajko ;
Trujic, Milos .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (02) :988-1004