Spanning eulerian subdigraphs avoiding k prescribed arcs in tournaments

Jørgen Bang-Jensen*, Hugues Déprés*, Anders Yeo*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

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 languageEnglish
Article number112129
JournalDiscrete Mathematics
Volume343
Issue number12
Number of pages7
ISSN0012-365X
DOIs
Publication statusPublished - Dec 2020

Keywords

  • Arc-connectivity
  • Avoiding prescribed arcs
  • Eulerian subdigraph
  • Semicomplete digraph
  • Tournament

Fingerprint

Dive into the research topics of 'Spanning eulerian subdigraphs avoiding k prescribed arcs in tournaments'. Together they form a unique fingerprint.

Cite this