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]. In particular, the conjecture holds for k≤4
Original language | English |
---|---|
Article number | 112129 |
Journal | Discrete Mathematics |
Volume | 343 |
Issue number | 12 |
Number of pages | 7 |
ISSN | 0012-365X |
DOIs | |
Publication status | Published - Dec 2020 |
Keywords
- Arc-connectivity
- Avoiding prescribed arcs
- Eulerian subdigraph
- Semicomplete digraph
- Tournament