2019/07/01 by Bang-Jensen, Jørgen, Depres, Hugues, Yeo, Anders
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1907.00853
A digraph is \bf eulerian if it is connected and every vertex has its in-degree equal to its out-degree. Having a spanning eulerian subdigraph is thus a weakening of having a hamiltonian cycle. A digraph is \bf semicomplete if it has no pair of non-adjacent vertices. A \bf tournament is a semicomplete digraph without directed cycles of length 2. Fraise and Thomassen \citefraisseGC3 proved that every (k+1)-strong tournament has a hamiltonian cycle which avoids any prescribed set of k arcs. In \citebangsupereuler the authors demonstrated that a number of results concerning vertex-connectivity and hamiltonian cycles in tournaments and have analogues when we replace vertex connectivity by arc-connectivity and hamiltonian cycles by spanning eulerian subdigraphs. They showed the existence of a smallest function f(k) such that every f(k)-arc-strong semicomplete digraph has a spanning eulerian subdigraph which avoids any prescribed set of k arcs. They proved that f(k)≤ ((k+1)2)/(4)+1 and also proved that f(k)=k+1 when k=2,3. Based on this they conjectured that f(k)=k+1 for all k≥ 0. In this paper we prove that f(k)≤ (\lceil(6k+1)/(5)\rceil).