Forward Arc Maximization for Hamilton Oriented Cycles and Paths in Generalizations of Tournaments
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908827654291456 |
|---|---|
| author | Guo, Q. Gutin, G. Lan, Y. Shao, Q. Yeo, A. Zhou, Y. |
| author_facet | Guo, Q. Gutin, G. Lan, Y. Shao, Q. Yeo, A. Zhou, Y. |
| contents | Gishboliner, Krivelevich, and Michaeli (2023) conjectured the following generalization of Dirac's theorem: If the minimum degree $δ$ of an $n$-vertex oriented graph $G$ is greater or equal to $n/2$, then $G$ has a Hamilton oriented cycle with at least $δ$ forward arcs. Freschi and Lo (2024) proved this conjecture. In this paper, we study the problem of maximizing the number of forward arcs in Hamilton oriented cycles/paths in generalizations of tournaments. We obtain characterizations for the maximum number of forward arcs in semicomplete multipartite digraphs and locally semicomplete digraphs. These characterizations lead to polynomial-time algorithms. Note that the above problems are NP-hard for some other generalizations of tournaments even though the Hamilton cycle problem is polynomial-time solvable for these digraph classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_10713 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Forward Arc Maximization for Hamilton Oriented Cycles and Paths in Generalizations of Tournaments Guo, Q. Gutin, G. Lan, Y. Shao, Q. Yeo, A. Zhou, Y. Combinatorics Gishboliner, Krivelevich, and Michaeli (2023) conjectured the following generalization of Dirac's theorem: If the minimum degree $δ$ of an $n$-vertex oriented graph $G$ is greater or equal to $n/2$, then $G$ has a Hamilton oriented cycle with at least $δ$ forward arcs. Freschi and Lo (2024) proved this conjecture. In this paper, we study the problem of maximizing the number of forward arcs in Hamilton oriented cycles/paths in generalizations of tournaments. We obtain characterizations for the maximum number of forward arcs in semicomplete multipartite digraphs and locally semicomplete digraphs. These characterizations lead to polynomial-time algorithms. Note that the above problems are NP-hard for some other generalizations of tournaments even though the Hamilton cycle problem is polynomial-time solvable for these digraph classes. |
| title | Forward Arc Maximization for Hamilton Oriented Cycles and Paths in Generalizations of Tournaments |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2602.10713 |