pith. sign in

arxiv: 1109.3741 · v1 · pith:I4O3CLWAnew · submitted 2011-09-17 · 🧮 math.CO

Immersing complete digraphs

classification 🧮 math.CO
keywords digraphscompletedigraphverticesconstructiondegreeimmersingimmersion
0
0 comments X
read the original abstract

We consider the problem of immersing the complete digraph on t vertices in a simple digraph. For Eulerian digraphs, we show that such an immersion always exists whenever minimum degree is at least t(t-1), and for t at most 4 minimum degree at least t-1 suffices. On the other hand, we show that there exist non-Eulerian digraphs with all vertices of arbitrarily high in- and outdegree which do not contain an immersion of the complete digraph on 3 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.