Making a tournament k $k$‐strong
Jørgen Bang‐Jensen, Kasper Skov Johansen, Anders Yeo · Journal of Graph Theory · 2022
Abstract A digraph is ‐strong if it has vertices and every induced subdigraph on at least vertices is strongly connected. A tournament is a digraph with no pair of nonadjacent vertices. We prove that every tournament on vertices can be made ‐strong by adding no more than arcs. This solves a conjecture from 1994. A digraph is semicomplete if there is at least one arc between any pair of distinct vertices . Since every semicomplete digraph contains a spanning tournament, the result above also holds for semicomplete digraphs. Our result also implies that for every , every semicomplete digraph on at least vertices can be made ‐strong by reversing no more than arcs.