Adding and Reversing Arcs in Semicomplete Digraphs

Source abstract

Let T be a semicomplete digraph on n vertices. Let a k ( T ) denote the minimum number of arcs whose addition to T results in a k -connected semicomplete digraph and let r k ( T ) denote the minimum number of arcs whose reversal in T results in a k -connected semicomplete digraph. We prove that if n [ges ]3 k −1, then a k ( T )= r k ( T ). We also show that this bound on n is best possible.