Yeo, A. and Bang-Jensen, J. (2004) Making a tournament k-arc-strong by reversing or deorienting arcs. Discrete Applied Mathematics, 136 (2-3).
Full text access: Open
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.
This is a Published version This version's date is: 15/02/2004 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/792de927-d9cd-8939-e7e9-dca6c99e0def/1/
Deposited by () on 23-Dec-2009 in Royal Holloway Research Online.Last modified on 23-Dec-2009