Making a tournament k $k$ ‐strong

A digraph isk${\bf{k}}$ ‐strong if it hasn ≥ k + 1$n\ge k+1$ vertices and every induced subdigraph on at leastn − k + 1$n-k+1$ vertices is strongly connected. A tournament is a digraph with no pair of nonadjacent vertices. We prove that every tournament onn ≥ k + 1$n\ge k+1$ vertices can be madek$k$ ‐strong by adding no more thank + 1 2$\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)$ arcs. This solves a conjecture from 1994. A digraph is semicomplete if there is at least one arc between any pair of distinct verticesx , y$x,y$ . Since every semicomplete digraph contains a spanning tournament, the result above also holds for semicomplete digraphs. Our result also implies that for everyk ≥ 2$k\ge 2$ , every semicomplete digraph on at least3 k − 1$3k-1$ vertices can be madek$k$ ‐strong by reversing no more thank + 1 2$\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)$ arcs.