Premium
A note on complete subdivisions in digraphs of large outdegree
Author(s) -
Kühn Daniela,
Osthus Deryk,
Young Andrew
Publication year - 2008
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20255
Subject(s) - digraph , combinatorics , subdivision , mathematics , tournament , transitive relation , order (exchange) , graph , discrete mathematics , archaeology , finance , economics , history
Mader conjectured that for all $\ell$ there is an integer $\delta^+(\ell)$ such that every digraph of minimum outdegree at least $\delta^+(\ell)$ contains a subdivision of a transitive tournament of order $\ell$ . 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 $\vec G$ be a digraph of order n whose minimum outdegree is at least d . Then $\vec G$ contains a subdivision of a complete digraph of order $\lfloor d^{2}/(8n^{3/2}) \rfloor$ . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 1–6, 2008