Peer-reviewedCC BY 4.0The Electronic Journal of Combinatorics
Powers of Hamiltonian Cycles in Randomly Augmented Pósa-Seymour Graphs
Abstract
We study the question of the least number of random edges that need to be added to a Pósa-Seymour graph, that is, a graph with minimum degree exceeding k/(k+1)n, to secure the existence of the m-th power of a Hamiltonian cycle, m>k. It turns out that, depending on k and m, this quantity may be captured by two types of thresholds, with one of them, called over-threshold, becoming dominant for large m. Indeed, for each k≥2 and m>m0(k), we establish asymptotically tight lower and upper bounds on the over-thresholds (provided they exist) and show that for infinitely many instances of m the two bounds coincide. In addition, we also determine the thresholds for some small values of k and m.
Related
- DEPTH OF POWERS OF EDGE IDEALS OF CYCLES AND STARLIKE TREES
- Enumerating Hamiltonian Paths and Cycles
- A Chvátal-type codegree condition for Hamiltonian cycles in k-uniform hypergraphs
- Covering powers of cycles with equivalence subgraphs
- On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof
BibTeX
@article{antoniuk2026powers,
title = {{Powers of Hamiltonian Cycles in Randomly Augmented Pósa-Seymour Graphs}},
author = {Sylwia Antoniuk and Andrzej Dudek and Andrzej Ruciński},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
month = oct,
doi = {10.37236/15044},
url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p26},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Powers of Hamiltonian Cycles in Randomly Augmented Pósa-Seymour Graphs
AU - Sylwia Antoniuk
AU - Andrzej Dudek
AU - Andrzej Ruciński
PY - 2026
DA - 2026/10/23
JO - The Electronic Journal of Combinatorics
DO - 10.37236/15044
UR - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p26
AB - We study the question of the least number of random edges that need to be added to a Pósa-Seymour graph, that is, a graph with minimum degree exceeding k/(k+1)n, to secure the existence of the m-th power of a Hamiltonian cycle, m>k. It turns out that, depending on k and m, this quantity may be captured by two types of thresholds, with one of them, called over-threshold, becoming dominant for large m. Indeed, for each k≥2 and m>m_0(k), we establish asymptotically tight lower and upper bounds on the over-thresholds (provided they exist) and show that for infinitely many instances of m the two bounds coincide. In addition, we also determine the thresholds for some small values of k and m.
SN - 1077-8926
ER -