We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Powers of Hamiltonian cycles in randomly augmented graphs.
- Authors
Dudek, Andrzej; Reiher, Christian; Ruciński, Andrzej; Schacht, Mathias
- Abstract
We study 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. It follows from the theorems of Dirac and of Komlós, Sarközy, and Szemerédi that for every k ≥ 1 and sufficiently large n already the minimum degree δ(G)≥kk+1n for an n‐vertex graph G alone suffices to ensure the existence of a kth power of a Hamiltonian cycle. Here we show that under essentially the same degree assumption the addition of just O(n) random edges ensures the presence of the (k + 1)st power of a Hamiltonian cycle with probability close to one.
- Subjects
HAMILTONIAN graph theory; RANDOM graphs
- Publication
Random Structures & Algorithms, 2020, Vol 56, Issue 1, p122
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.20870