Spanning 3-strong tournaments in 5-strong semicomplete digraphs (Q6080123)

A digraph \(D\) is a tournament (resp. semicomplete digraph) if there is precisely (resp. at least) one arc between any pair of distinct vertices of \(D\). A digraph is strong if it has a directed path from \(x\) to \(y\) for every ordered pair of distinct vertices \(x\) and \(y\), and it is \(k\)-strong if it has at least \(k + 1\) vertices and remains strong when we delete any set of at most \(k-1\) vertices. \textit{J. Bang-Jensen} proved in [J. Graph Theory 14, No. 3, 371--390 (1990; Zbl 0703.05026)] that every strong semicomplete digraph contains a Hamiltonian cycle, which can be stated as every strong semicomplete digraph contains a spanning strong tournament. It is of interest to ask whether there is a bound \(f(k)\) such that every \(l\)-strong semicomplete digraph with \(l\ge f(k)\) contains a spanning \(k\)-strong tournament. In 1990, Bang-Jensen and Thomassen (see [Bang-Jensen, loc. cit.]) proved that every \(5k\)-strong semicomplete digraph contains a spanning \(k\)-strong tournament, thus \(f(k)\) exists and \(f(k)\le 5k\). In [Discrete Appl. Math. 79, No. 1--3, 119--125 (1997; Zbl 0884.05047)], \textit{Y. Guo} proved that \(f(k)\le 3k-2\). \textit{J. Bang-Jensen} and \textit{T. Jordán} [Discrete Math. 310, No. 9, 1424--1428 (2010; Zbl 1221.05172)] constructed an infinite family of \(( 2k - 2 )\)-strong semicomplete digraphs containing no spanning \(k\)-strong tournament, which means that \(f(k)\ge 2k-1\). And they conjectured that equality holds: For every positive integer \(k\), every \(( 3k - 2 )\)-strong semicomplete digraph contains a spanning \(k\)-strong tournament. While the case \(k=1\) clearly holds and \(k=2\) has been verified, the current paper proves the conjecture for the case \(k=3\).