Powers of Hamiltonian cycles in randomly augmented Pósa-Seymour graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909978106789888 |
|---|---|
| author | Antoniuk, Sylwia Dudek, Andrzej Ruciński, Andrzej |
| author_facet | Antoniuk, Sylwia Dudek, Andrzej Ruciński, Andrzej |
| contents | 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 $\frac 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\ge2$ 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_23886 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Powers of Hamiltonian cycles in randomly augmented Pósa-Seymour graphs Antoniuk, Sylwia Dudek, Andrzej Ruciński, Andrzej Combinatorics 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 $\frac 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\ge2$ 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$. |
| title | Powers of Hamiltonian cycles in randomly augmented Pósa-Seymour graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.23886 |