Strong arc decompositions of split digraphs

A strong arc decomposition of a digraph (Formula presented.) is a partition of its arc set (Formula presented.) into two sets (Formula presented.) such that the digraph (Formula presented.) is strong for (Formula presented.). Bang-Jensen and Yeo conjectured that there is some (Formula presented.) such that every (Formula presented.) -arc-strong digraph has a strong arc decomposition. They also proved that with one exception on four vertices every 2-arc-strong semicomplete digraph has a strong arc decomposition. Bang-Jensen and Huang extended this result to locally semicomplete digraphs by proving that every 2-arc-strong locally semicomplete digraph which is not the square of an even cycle has a strong arc decomposition. This implies that every 3-arc-strong locally semicomplete digraph has a strong arc decomposition. A split digraph is a digraph whose underlying undirected graph is a split graph, meaning that its vertices can be partitioned into a clique and an independent set. Equivalently, a split digraph is any digraph which can be obtained from a semicomplete digraph (Formula presented.) by adding a new set (Formula presented.) of vertices and some arcs between (Formula presented.) and (Formula presented.). In this paper, we prove that every 3-arc-strong split digraph has a strong arc decomposition which can be found in polynomial time and we provide infinite classes of 2-strong split digraphs with no strong arc decomposition. We also pose a number of open problems on split digraphs.