Spanning Trees of Dense Directed Graphs
Richard Mycroft, Tássio Naia · Electronic Notes in Theoretical Computer Science · 2019
In the nineties, Komlós, Sárközy and Szemerédi confirmed a conjecture of Bollobás, 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 .