Abstract
Fraise and Thomassen (1987) proved that every (k+1)-strong tournament has a hamiltonian cycle which avoids any prescribed set of k arcs. Bang-Jensen, Havet and Yeo showed in Bang-Jensen et al. (2019) that a number of results concerning vertex-connectivity and hamiltonian cycles in tournaments have analogues when we replace vertex connectivity by arc-connectivity and hamiltonian cycles by spanning eulerian subdigraphs. They proved the existence of a smallest function f(k) with the property that every f(k)-arc-strong semicomplete digraph has a spanning eulerian subdigraph which avoids any prescribed set of k arcs by showing that [Formula presented]. They conjectured that every (k+1)-arc-strong semicomplete digraph has a spanning eulerian subdigraph which avoids any prescribed set of k arcs and verified this for k=2,3. In this paper we prove that [Formula presented].
| Original language | English |
|---|---|
| Article number | 112129 |
| Journal | Discrete Mathematics |
| Volume | 343 |
| Issue number | 12 |
| DOIs | |
| Publication status | Published - Dec 2020 |
Keywords
- Arc-connectivity
- Avoiding prescribed arcs
- Eulerian subdigraph
- Semicomplete digraph
- Tournament
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics