Spanning eulerian subdigraphs avoiding k prescribed arcs in tournaments

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

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

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 languageEnglish
Article number112129
JournalDiscrete Mathematics
Volume343
Issue number12
DOIs
Publication statusPublished - Dec 2020

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

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

Cite this