Immersion of complete digraphs in Eulerian digraphs

Abstract

A digraph $G$ \emph{immerses} a digraph $H$ if there is an injection $f:V(H)\to V(G)$ and a collection of pairwise edge-disjoint directed paths $P_{uv}$, for $uv\in E(H)$, such that $P_{uv}$ starts at $u$ and ends at $v$. We prove that every Eulerian digraph with minimum out-degree $t$ immerses a complete digraph on $\Omega (t)$ vertices, thus answering a question of DeVos, Mcdonald, Mohar, and Scheide.

arXiv comment17 pages; fixed typos