A note on complete subdivisions in digraphs of large outdegree

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

Mader conjectured that for all l there is an integer delta(+)(l) such that every digraph of minimum outdegree at least delta(+)(l) contains a subdivision of a transitive tournament of order l. In this note, we observe that if the minimum outdegree of a digraph is sufficiently large compared to its order then one can even guarantee a subdivision of a large complete digraph. More precisely, let (G) over bar be a digraph of order n whose minimum outdegree is at least d. Then (G) over bar contains a subdivision of a complete digraph of order left perpendicular d(2)/(8n(3/2)) right perpendicular. (c) 2007 Wiley Periodicals, Inc.
Original languageEnglish
Pages (from-to)1-6
Number of pages6
JournalJournal of Graph Theory
Volume57
Issue number1
Early online date1 Jan 2007
DOIs
Publication statusPublished - 1 Jan 2008

Keywords

  • subdivision
  • digraph
  • topological minor

Fingerprint

Dive into the research topics of 'A note on complete subdivisions in digraphs of large outdegree'. Together they form a unique fingerprint.

Cite this