Spanning Trees of Dense Directed Graphs

Abstract In the nineties, Komlos, Sarkozy and Szemeredi confirmed a conjecture of Bollobas, showing that for every positive α, Δ and sufficiently large n, every graph with minimum degree (1/2 + α)n contains every tree of order n and maximum degree at most Δ. We obtain a directed graph analogue of their result, where the minimum degree is replaced by minimum semidegree (which is the minimum of all in- and out-degrees over all vertices) and the maximum degree is replaced by the maximum degree of the underlying graph (i.e., the maximum degree of the graph we obtain by ignoring the orientation of edges). In fact, we prove a stronger result, which states a sufficient condition for a tree of order n to be contained in every directed graph of order n and minimum semidegree (1/2 + α)n. This result implies that for all positive real α and sufficiently large n every directed graph of order n with minimum semidegree (1/2+α)n contains almost every spanning oriented tree T of order n.