Spanning 2-strong tournaments in 3-strong semicomplete digraphs

作者：Bang Jensen Jorgen^*; Jordan Tibor

来源：Discrete Mathematics, 2010, 310(9): 1424-1428.

DOI：10.1016/j.disc.2009.04.019

• Connectivity of digraphs
• Semicomplete digraph
• Tournament

We prove that every 3-strong semicomplete digraph on at least 5 vertices contains a spanning 2-strong tournament. Our proof is constructive and implies a polynomial algorithm for finding a spanning 2-strong tournament in a given 3-strong semicomplete digraph. We also show that there are infinitely many (2k - 2)-strong semicomplete digraphs which contain no spanning k-strong tournament and conjecture that every (2k - 1)-strong semicomplete digraph which is not the complete digraph k(2k)(*) on 2k vertices contains a spanning k-strong tournament.

• 出版日期2010-5-6