Bang-Jensen, J. and Yeo, A. (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 Submitted version This version's date is: 15/2/2004 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/792de927-d9cd-8939-e7e9-dca6c99e0def/8/
Deposited by Research Information System (atira) on 18-Nov-2014 in Royal Holloway Research Online.Last modified on 18-Nov-2014