ON POWERS OF HAMILTON CYCLES IN RAMSEY-TURAN THEORY

被引：0

作者：

Chen, Ming ^{[1
]}

Han, Jie ^{[2
,3
]}

Tang, Yantao ^{[4
]}

Yang, Donglei ^{[5
]}

机构：

[1] Jiangsu Normal Univ, Sch Math & Stat, Xuzhou 221116, Peoples R China

[2] Beijing Inst Technol, Sch Sch Math & Stat, Beijing 100081, Peoples R China

[3] Beijing Inst Technol, Ctr Appl Math, Beijing 100081, Peoples R China

[4] Shandong Univ, Zhongtai Securities Inst Financial Studies, Jinan 250100, Peoples R China

[5] Shandong Univ, Sch Math, Jinan 250100, Peoples R China

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2024年 / 38卷 / 03期

关键词：

powers of Hamilton cycles; absorption method; Ramsey-Turan theory; GRAPHS; SQUARE;

D O I：

10.1137/24M163709X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We prove that for r is an element of N with r >= 2 and mu > 0, there exist alpha > 0 and n(0) such that for every n >= n(0) , every n-vertex graph G with delta(G) >= (1- 1/r + mu) n and alpha(G) <= alpha n contains an r th power of a Hamilton cycle. We also show that the minimum degree condition is asymptotically sharp for r = 2,3 and the r = 2 case was recently conjectured by Staden and Treglown.

引用

页码：2489 / 2508

页数：20

共 21 条

[1] Triangle Factors of Graphs Without Large Independent Sets and of Weighted Graphs
Balogh, Jozsef
Molla, Theodore
Sharifzadeh, Maryam
[J]. RANDOM STRUCTURES & ALGORITHMS, 2016, 49 (04) : 669 - 693
[2] Embedding clique-factors in graphs with low l-independence number
Chang, Fan
Han, Jie
Kim, Jaehoon
Wang, Guanghui
Yang, Donglei
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2023, 161 : 301 - 330
[3] Chen M, 2022, Arxiv, DOI arXiv:2207.03058
[4] Dirac G. A., 1952, Proc. Lond. Math. Soc., P69, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]
[5] MORE RESULTS ON RAMSEY TURAN TYPE PROBLEMS
ERDOS, P
HAJNAL, A
SOS, VT
SZEMEREDI, E
[J]. COMBINATORICA, 1983, 3 (01) : 69 - 81
[6] ERDOS P., 1982, Studia Sci. Math. Hungar, V14, P27
[7] THE SQUARE OF A HAMILTONIAN CYCLE
FAN, GH
HAGGKVIST, R
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1994, 7 (02) : 203 - 212
[8] THE SQUARE OF PATHS AND CYCLES
FAN, GH
KIERSTEAD, HA
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 63 (01) : 55 - 64
[9] HAGGKVIST R., 1979, On F-Hamiltonian Graphs
[10] Clique-factors in graphs with sublinear ι-independence number
Han, Jie
Hu, Ping
Wang, Guanghui
Yang, Donglei
[J]. COMBINATORICS PROBABILITY & COMPUTING, 2023, 32 (04) : 665 - 681

← 1 2 3 →