DIKUL - logo
(UL)
  • Immersing complete digraphs
    DeVos, Matt ...
    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 \le 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 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.
    Source: European journal of combinatorics = Journal européen de combinatoire = Europäische Zeitschrift für Kombinatorik. - ISSN 0195-6698 (Vol. 33, iss. 6, 2012, str. 1294-1302)
    Type of material - article, component part
    Publish date - 2012
    Language - english
    COBISS.SI-ID - 16317017

    Link(s):

    http://dx.doi.org/10.1016/j.ejc.2012.02.002

Shelf entry