Oriented Hamiltonian Paths in Tournaments: Stability under Arc Deletion
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_ | 1866912756432633856 |
|---|---|
| author | Sahili, Mahabba El Zein, Ayman El |
| author_facet | Sahili, Mahabba El Zein, Ayman El |
| contents | Havet and Thomassé proved that every tournament of order $n\geq 8$ contains every oriented Hamiltonian path, which was conjectured by Rosenfeld. Recently, it was shown that in any tournament $T$ of order $n\geq 8$, there exists an arc $e$ such that $T-e$ contains any oriented Hamiltonian path. A natural extension of this problem is to study the stability of this property under arbitrary arc deletion. In this paper, we prove that every arc $e$ in a tournament $T$ of order $n\geq 8$ satisfies that $T-e$ contains every oriented Hamiltonian path, except for some explicitly described exceptions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_09332 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Oriented Hamiltonian Paths in Tournaments: Stability under Arc Deletion Sahili, Mahabba El Zein, Ayman El Combinatorics Havet and Thomassé proved that every tournament of order $n\geq 8$ contains every oriented Hamiltonian path, which was conjectured by Rosenfeld. Recently, it was shown that in any tournament $T$ of order $n\geq 8$, there exists an arc $e$ such that $T-e$ contains any oriented Hamiltonian path. A natural extension of this problem is to study the stability of this property under arbitrary arc deletion. In this paper, we prove that every arc $e$ in a tournament $T$ of order $n\geq 8$ satisfies that $T-e$ contains every oriented Hamiltonian path, except for some explicitly described exceptions. |
| title | Oriented Hamiltonian Paths in Tournaments: Stability under Arc Deletion |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.09332 |