Bang-Jensen–DeVos–Mütze conjecture on strong tournaments in semicomplete digraphs
Bang-Jensen–DeVos–Mütze conjecture on strong tournaments in semicomplete digraphs
Let 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 -strong if it has at least vertices and remains strongly connected after the deletion of any subset of vertices. A tournament is an oriented complete graph, and a spanning subdigraph contains all vertices of .
Bang-Jensen–DeVos–Mütze conjecture. Every -strong semicomplete digraph on at least vertices contains a spanning -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
Sign in to submit a solution.
No solutions have been posted yet.