Immersing complete digraphs

We consider the problem of immersing the complete digraph on tt vertices in a simple digraph. For Eulerian digraphs, we show that such an immersion always exists whenever the minimum degree is at least t(t−1)t(t−1), and, for t≤4t≤4, minimum degree at least t−1t−1 suffices. On the other hand, we show that there exist non-Eulerian digraphs with all vertices of arbitrarily high indegree and outdegree which do not contain an immersion of the complete digraph on three vertices. As a side result, we obtain a construction of digraphs with large outdegree in which all cycles have odd length, simplifying a former construction of such graphs by Thomassen.

► Every Eulerian digraph with minimum degree at least t(t−1)t(t−1) has a K→t-immersion. ► If t≤4t≤4, we can replace t(t−1)t(t−1) with t−1t−1 in the above result. ► There are non-Eulerian digraphs with arbitrarily high minimum degree but no K→3-immersion.