zbMATH — the first resource for mathematics

Making a tournament \(k\)-arc-strong by reversing or deorienting arcs. (English) Zbl 1035.05045
Summary: We prove that every tournament \(T=(V,A)\) on \(n \geq 2k+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.

05C20 Directed graphs (digraphs), tournaments
05C40 Connectivity
Full Text: DOI
[1] J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, London, 2000, xxii+754pp. · Zbl 1170.05002
[2] Bang-Jensen, J.; Jordán, T., Adding and reversing arcs in semicomplete digraphs, Combin. probab. comput., 7, 17-25, (1998) · Zbl 0892.05019
[3] Thomassen, C., Configurations in graphs of large minimum degree, connectivity, or chromatic number, Ann. New York acad. sci., 555, 402-412, (1989)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.