2026/07/19 by Jia Zhou, Jørgen Bang-Jensen, Tong Zhou +1
#math.CO
Let k be a positive integer. Jackson and Thomassen conjectured in 1989 that there exists an integer function f(k) such that every f(k)-strong digraph admits a spanning k-strong oriented subdigraph. They even conjectured that one can take f(k)=2k [Ann. N. Y. Acad. Sci. 555 (1989) 402-412]. Already the existence of f(2) is open for general digraphs. Thomassen proved that f(2)=4 for symmetric digraphs. For general k, the existence of f(k) was only known for locally semicomplete digraphs and quasi-transitive digraphs. Guo proved that every (3k-2)-strong locally semicomplete digraph contains a spanning k-strong local tournament [Discrete Appl. Math. 79 (1997) 119--125]. One can deduce from Guo's result that we have f(k)≤ 3k-2 for quasi-transitive digraphs. In this paper, we prove the existence of f(k) for two subclasses of the semicomplete multipartite digraphs, namely extended semicomplete digraphs and semicomplete split digraphs. We prove that every (4k+1)-strong extended semicomplete digraph contains a spanning k-strong oriented subdigraph and every 5k-strong semicomplete split digraph contains a spanning k-strong oriented subdigraph. The first result implies that for the large class of digraphs which can be obtained from some semicomplete digraph S on at least 3 vertices by substituting arbitrary digraphs for each vertex of S we also have f(k)≤ 4k+1.