Trees and tree-like structures in dense digraphs

Publication date 16 December 2020

Directed graphs (digraphs), tournaments (05C20)

Abstract: We prove that every oriented tree on

n

vertices with bounded maximum degree appears as a spanning subdigraph of every directed graph on

n

vertices with minimum semidegree at least

n / 2 + m a t h r m o (n)

. This can be seen as a directed graph analogue of a well-known theorem of Koml'os, S'ark"ozy and Szemer'edi. Our result for trees follows from a more general result, allowing the embedding of arbitrary orientations of a much wider class of spanning "tree-like" structures, such as a collection of at most

m a t h r m o (n^{1 / 4})

vertex-disjoint cycles and subdivisions of graphs

H

with

| H | < n^{(l o g n)^{- 1 / 2}}

in which each edge is subdivided at least once.

This page was built for publication: Trees and tree-like structures in dense digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6356287)