High powers of Hamiltonian cycles in randomly augmented graphs

We investigate the existence of powers of Hamiltonian cycles in graphs with large minimum degree to which some additional edges have been added in a random manner. For all integers k ⩾ 1 , r ⩾ 0, and ℓ ⩾ ( r + 1 ) r, and for any α > k k + 1 we show that adding O ( n 2 − 2 ∕ ℓ ) random edges to an...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2021-09, Vol.98 (2), p.255-284
Main Authors: Antoniuk, Sylwia, Dudek, Andrzej, Reiher, Christian, Ruciński, Andrzej, Schacht, Mathias
Format: Article
Language:English
Subjects:
augmented graphs
Graph theory
Graphs
powers of Hamilton cycles
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We investigate the existence of powers of Hamiltonian cycles in graphs with large minimum degree to which some additional edges have been added in a random manner. For all integers k ⩾ 1 , r ⩾ 0, and ℓ ⩾ ( r + 1 ) r, and for any α > k k + 1 we show that adding O ( n 2 − 2 ∕ ℓ ) random edges to an n‐vertex graph G with minimum degree at least α n yields, with probability close to one, the existence of the ( k ℓ + r )‐th power of a Hamiltonian cycle. In particular, for r = 1 and ℓ = 2 this implies that adding O ( n ) random edges to such a graph G already ensures the ( 2 k + 1 )‐st power of a Hamiltonian cycle (proved independently by Nenadov and Trujić). In this instance and for several other choices of k , ℓ, and r we can show that our result is asymptotically optimal.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.22691