Spanning eulerian subdigraphs avoiding k prescribed arcs in tournaments

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

*Kontaktforfatter for dette arbejde

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstrakt

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

OriginalsprogEngelsk
Artikelnummer112129
TidsskriftDiscrete Mathematics
Vol/bind343
Udgave nummer12
Antal sider7
ISSN0012-365X
DOI
StatusUdgivet - dec. 2020

Fingeraftryk Dyk ned i forskningsemnerne om 'Spanning eulerian subdigraphs avoiding k prescribed arcs in tournaments'. Sammen danner de et unikt fingeraftryk.

  • Citationsformater