Immersing complete digraphs

DOI10.1016/J.EJC.2012.02.002MaRDI QIDQ427820zbMATHOpenAlexFDO

Authors Matt DeVos, Jessica McDonald, Bojan Mohar, Diego Scheide

Publication date 18 June 2012

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.3741

zbMATH Keywords

Eulerian digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

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.

Recommendations

• Immersion of transitive tournaments in digraphs with large minimum outdegree
• Complete graph immersions and minimum degree
• A minimum degree condition forcing complete graph immersion
• Strong immersion is a well-quasi-ordering for semicomplete digraphs
• Constructing graphs with no immersion of large complete graphs

Cites work

• scientific article; zbMATH DE number 4104981 (Why is no real title available?)
• scientific article; zbMATH DE number 3488914 (Why is no real title available?)
• scientific article; zbMATH DE number 1498519 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A note on complete subdivisions in digraphs of large outdegree
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Degree and local connectivity in digraphs
• Even cycles in directed graphs
• Existence of vertices of local connectivity \(k\) in digraphs of large outdegree
• Graph theory
• Immersing small complete graphs
• Konstruktion aller n-fach kantenzusammenhaengenden Digraphen
• On topological tournaments of order 4 in digraphs of outdegree 3

Cited in

(9)

• Immersion of transitive tournaments in digraphs with large minimum outdegree
• Constructing graphs with no immersion of large complete graphs
• Immersion of complete digraphs in Eulerian digraphs
• Biclique immersions in graphs with independence number 2
• Subdivisions in digraphs of large out-degree or large dichromatic number
• Subdivisions in dicritical digraphs with large order or digirth
• scientific article; zbMATH DE number 5379347 (Why is no real title available?)
• Immersing small complete graphs
• Tournament immersion and cutwidth

This page was built for publication: Immersing complete digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q427820)