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 language | English |
---|---|
Pages (from-to) | 1-6 |
Number of pages | 6 |
Journal | Journal of Graph Theory |
Volume | 57 |
Issue number | 1 |
Early online date | 1 Jan 2007 |
DOIs | |
Publication status | Published - 1 Jan 2008 |
Keywords
- subdivision
- digraph
- topological minor