Making a tournament k-strong

A digraph is k‐strong if it has n ≥ k+1 vertices andeveryinduced subdigraph on at least n-k+1verticesis strongly connected. Atournament is a digraphwith no pair of nonadjacent vertices. We prove that everytournament on n ≥ k+1 vertices can be made k‐strong by adding no more than (k+1/2) arcs. This solves a conjecture from1994. A digraph is semicomplete if there is at least one arc between any pairof distinct vertices x, y. Sinceevery semicomplete digraph contains a spanning tournament, the result abovealso holds for semicomplete digraphs. Our result also implies that for every K≥2, every semicomplete digraph on atleast 3k−1vertices can be made k‐strong by reversing no more than (k+1/2) arcs.