Abstract
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.
Funding Information
  • Simons Foundation (522400)
  • European Research Council (PEPCo 724903)
  • Narodowe Centrum Nauki (2018/29/B/ST1/00426)

This publication has 10 references indexed in Scilit: