Complementary cycles containing prescribed vertices in tournaments Original Research Article

We prove that if T is a tournament on n⩾7 vertices and x,y are distinct vertices of T with the property that T remains 2-connected if we delete the arc between x and y, then there exist disjoint 3-cycles Cx,Cy such that x∈V(Cx) and y∈V(Cy). This is best possible in terms of the connectivity assumption. Using this result, we prove that under the same connectivity assumption and if n⩾8, then T also contains complementary cycles C′x,C′y (i.e. V(C′x)∪V(C′y)=V(T) and V(C′x)∩V(C′y)=∅) such that x∈V(C′x) and y∈V(C′y) for every choice of distinct vertices x,y∈V(T). Again this is best possible in terms of the connectivity assumption. It is a trivial consequence of our result that one can decide in polynomial time whether a given tournament T with special vertices x,y contains disjoint cycles Cx,Cy such that x∈V(Cx) and y∈V(Cy). This problem is NP-complete for general digraphs and furthermore there is no degree of strong connectivity which suffices to guarantee such cycles in a general digraph.