Powers of Hamilton cycles in dense graphs perturbed by a random geometric graph

被引:1
作者
Diaz, Alberto Espuny [1 ]
Hyde, Joseph [2 ]
机构
[1] Tech Univ Ilmenau, Inst Math, Weimarer Str 25, D-98684 Ilmenau, Germany
[2] Univ Victoria, Math & Stat, David Turpin Bldg, Victoria, BC V8W 2Y2, Canada
基金
英国科研创新办公室; 欧洲研究理事会;
关键词
RANDOM EDGES; THRESHOLD; SQUARE;
D O I
10.1016/j.ejc.2023.103848
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G be a graph obtained as the union of some n-vertex graph H-n with minimum degree delta(H-n) >= alpha n and a d-dimensional random geometric graph G(d)(n,r). We investigate under which conditions for r the graph G will a.a.s. contain the kth power of a Hamilton cycle, for any choice of H-n. We provide asymptotically optimal conditions for r for all values of alpha, d and k. This has applications in the containment of other spanning structures, such as F-factors.
引用
收藏
页数:14
相关论文
共 53 条
[31]   Tilings in randomly perturbed graphs: Bridging the gap between Hajnal-Szemeredi and Johansson-Kahn-Vu [J].
Han, Jie ;
Morris, Patrick ;
Treglown, Andrew .
RANDOM STRUCTURES & ALGORITHMS, 2021, 58 (03) :480-516
[32]   Hamiltonicity in randomly perturbed hypergraphs [J].
Han, Jie ;
Zhao, Yi .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 144 :14-31
[33]  
Janson S., 2000, WIL INT S D, Vfirst
[34]   Spanning trees in randomly perturbed graphs [J].
Joos, Felix ;
Kim, Jaehoon .
RANDOM STRUCTURES & ALGORITHMS, 2020, 56 (01) :169-219
[35]   THE THRESHOLD FOR THE SQUARE OF A HAMILTON CYCLE [J].
Kahn, Jeff ;
Narayanan, Bhargav ;
Park, Jinyoung .
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2021, 149 (08) :3201-3208
[36]   Tiling Turan theorems [J].
Komlós, J .
COMBINATORICA, 2000, 20 (02) :203-218
[37]  
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
[38]  
2-P
[39]  
KOMLOS J, 1998, ANN COMB, V2, P43
[40]  
Korsunov A.D, 1977, Metody Diskretn. Anal., V31, P17