Bang-Jensen–DeVos–Mütze conjecture on strong tournaments in semicomplete digraphs

From papers

Let DD be a semicomplete digraph, meaning that for every pair of distinct vertices, at least one of the two possible directed arcs is present. A digraph is kk-strong if it has at least k+1k+1 vertices and remains strongly connected after the deletion of any subset of k1k-1 vertices. A tournament is an oriented complete graph, and a spanning subdigraph contains all vertices of DD.

Bang-Jensen–DeVos–Mütze conjecture. Every (2k1)(2k-1)-strong semicomplete digraph on at least 2k+12k+1 vertices contains a spanning kk-strong tournament.

The source presents this as a conjecture supported by its arc-connectivity analogue, while also giving sharpness results for the order and connectivity bounds and a counterexample for a broader class of almost semicomplete digraphs. Its status is not resolved in the supplied text.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Tong Zhou, Jørgen Bang-Jensen, Jia Zhou and Jin Yan, “K-Arc-Strong Orientations Of Semicomplete Digraphs”, arXiv:2607.17116 (2026).

Solutions 0

No solutions have been posted yet.