Hamiltonian Cycles Avoiding Prescribed Arcs in Tournaments

In [6], Thomassen conjectured that if I is a set of k \Gamma 1 arcs in a k-strong tournament T , then T \Gamma I has a Hamiltonian cycle. This conjecture was proved by Fraisse and Thomassen [3]. We prove the following stronger result. Let T = (V; A) be a k-strong tournament on n vertices and let X 1 ; X 2 ; : : : ; X l be a partition of the vertex set V of T such that jX 1 j jX 2 j : : : jX l j n=2. If k P l\Gamma1 i=1 bjX i j=2c + jX l j, then T \Gamma [ l i=1 fxy 2 A : x; y 2 X i g has a Hamiltonian cycle. 1 Introduction In [6], Thomassen conjectured that if I is a set of k \Gamma 1 arcs in a k-strong tournament T , then T \Gamma I has a Hamiltonian cycle. This conjecture was proved by Fraisse and Thomassen [3]. This result is sharp since the deletion of a set I of k arcs from a k-strong tournament may create a vertex of indegree or outdegree 0. However, the authors of [6] realized that, for some sets I, their bound was far from being the best possible (see, e.g., Sectio..