K-Arc-Strong Orientations Of Semicomplete Digraphs

Results by Jackson and Frank imply that every 2k-arc-strong digraph D contains a spanning k-arc-strong oriented subdigraph.

This is best possible, even for very dense digraphs.

A digraph is semicomplete if at least one of the arcs xy,yx is present for every pair of distinct vertices x,y.

A tournament has exactly one of xy,yx for every such pair.

Clearly every semicomplete digraph D contains a spanning tournament T which is obtained by deleting one arc from every 2-cycle of D.

We prove that every (2k-1)-arc-strong semicomplete digraph on at least 2k+1 vertices contains a spanning k-arc-strong tournament.

Both bounds 2k-1 and 2k+1 are best possible.

The proof uses Frank's general orientation theorem for graphs as well as counting arguments based on the semicomplete structure.