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 条
[1]   EMBEDDING ARBITRARY GRAPHS OF MAXIMUM DEGREE 2 [J].
AIGNER, M ;
BRANDT, S .
JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 1993, 48 :39-51
[2]   Rainbow trees in uniformly edge-colored graphs [J].
Aigner-Horev, Elad ;
Hefetz, Dan ;
Lahiri, Abhiruk .
RANDOM STRUCTURES & ALGORITHMS, 2023, 62 (02) :287-303
[3]   RAINBOW HAMILTON CYCLES IN RANDOMLY COLORED RANDOMLY PERTURBED DENSE GRAPHS [J].
Aigner-Horev, Elad ;
Hefetz, Dan .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (03) :1569-1577
[4]   H-factors in dense graphs [J].
Alon, N ;
Yuster, R .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1996, 66 (02) :269-282
[5]  
Alon N, 1999, ARS COMBINATORIA, V52, P296
[6]   How many randomly colored edges make a randomly colored dense graph rainbow Hamiltonian or rainbow connected? [J].
Anastos, Michael ;
Frieze, Alan .
JOURNAL OF GRAPH THEORY, 2019, 92 (04) :405-414
[7]   Powers of Hamiltonian cycles in randomly augmented Dirac graphs-The complete collection [J].
Antoniuk, Sylwia ;
Dudek, Andrzej ;
Rucinski, Andrzej .
JOURNAL OF GRAPH THEORY, 2023, 104 (04) :811-835
[8]   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
[9]   Rainbow perfect matchings and Hamilton cycles in the random geometric graph [J].
Bal, Deepak ;
Bennett, Patrick ;
Perez-Gimenez, Xavier ;
Pralat, Pawel .
RANDOM STRUCTURES & ALGORITHMS, 2017, 51 (04) :587-606
[10]   Rainbow connectivity of randomly perturbed graphs [J].
Balogh, Jozsef ;
Finlay, John ;
Palmer, Cory .
JOURNAL OF GRAPH THEORY, 2025, 109 (02) :101-106