Making a tournament k-arc-strong by reversing or deorienting arcs

Abstract

We prove that every tournament T=(V,A) on n2k+1 vertices can be made k-arc-strong by reversing no more than k(k+1)/2 arcs. This is best possible as the transitive tournament needs this many arcs to be reversed. We show that the number of arcs we need to reverse in order to make a tournament k-arc-strong is closely related to the number of arcs we need to reverse just to achieve in- and out-degree at least k. We also consider, for general digraphs, the operation of deorienting an arc which is not part of a 2-cycle. That is we replace an arc xy such that yx is not an arc by the 2-cycle xyx. We prove that for every tournament T on at least 2k+1 vertices, the number of arcs we need to reverse in order to obtain a k-arc-strong tournament from T is equal to the number of arcs one needs to deorient in order to obtain a k-arc-strong digraph from T. Finally, we discuss the relations of our results to related problems and conjectures.