Backward Arcs in Hamilton Oriented Cycles and Paths in Directed Graphs with Independence Number Two
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914417420009472 |
|---|---|
| author | Gerke, S. Guo, Q. Gutin, G. Hao, Y. Veeranonchai, W. Yeo, A. |
| author_facet | Gerke, S. Guo, Q. Gutin, G. Hao, Y. Veeranonchai, W. Yeo, A. |
| contents | In a digraph $D=(V,A)$, an oriented path is a sequence $P=x_1x_2\dots x_p$ of distinct vertices such that either $x_ix_{i+1}\in A$ or $x_{i+1}x_{i}\in A$ or both for every $i\in [p-1]$. If $x_ix_{i+1}\in A$ in $P$, then $x_ix_{i+1}$ is a forward arc of $P$; otherwise, $x_{i+1}x_{i}$ is a backward arc. The independence number $α(D)$ is the maximum integer $p$ such that $D$ has a set of $p$ vertices where there is no arc between any pair of vertices. A digraph is $k$-connected if its underlying undirected graph is $k$-connected. Freschi and Lo (JCT-B 2024) proved that every $n$-vertex oriented graph with minimum degree $δ\ge n/2$ has a Hamilton oriented cycle with at most $n-δ$ backward arcs. We prove that every 2-connected digraph $D$ with $α(D)\le 2$ has a Hamilton oriented cycle with at most five backward arcs, and every 1-connected digraph $D$ with $α(D)\le 2$ has a Hamilton oriented path with at most two backward arcs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_22993 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Backward Arcs in Hamilton Oriented Cycles and Paths in Directed Graphs with Independence Number Two Gerke, S. Guo, Q. Gutin, G. Hao, Y. Veeranonchai, W. Yeo, A. Combinatorics Discrete Mathematics In a digraph $D=(V,A)$, an oriented path is a sequence $P=x_1x_2\dots x_p$ of distinct vertices such that either $x_ix_{i+1}\in A$ or $x_{i+1}x_{i}\in A$ or both for every $i\in [p-1]$. If $x_ix_{i+1}\in A$ in $P$, then $x_ix_{i+1}$ is a forward arc of $P$; otherwise, $x_{i+1}x_{i}$ is a backward arc. The independence number $α(D)$ is the maximum integer $p$ such that $D$ has a set of $p$ vertices where there is no arc between any pair of vertices. A digraph is $k$-connected if its underlying undirected graph is $k$-connected. Freschi and Lo (JCT-B 2024) proved that every $n$-vertex oriented graph with minimum degree $δ\ge n/2$ has a Hamilton oriented cycle with at most $n-δ$ backward arcs. We prove that every 2-connected digraph $D$ with $α(D)\le 2$ has a Hamilton oriented cycle with at most five backward arcs, and every 1-connected digraph $D$ with $α(D)\le 2$ has a Hamilton oriented path with at most two backward arcs. |
| title | Backward Arcs in Hamilton Oriented Cycles and Paths in Directed Graphs with Independence Number Two |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2603.22993 |