Theoretical analysis demonstrates conditions for unavoidable oriented trees in finite directed graphs, indicating structural bounds on subdivided in-star subgraphs.
We ask the question, Which oriented trees [Formula: see text] must be contained as subgraphs in every finite directed graph of sufficiently large minimum out-degree? We formulate the following simple condition: all vertices in [Formula: see text] of in-degree at least 2 must be on the same “level” in the natural height function of [Formula: see text]. We prove this condition to be necessary and conjecture it to be sufficient. In support of our conjecture, we prove it for a fairly general class of trees. An essential tool in the latter proof, and a question interesting in its own right, is finding large subdivided in-stars in a directed graph of large minimum out-degree. We conjecture that any digraph and oriented graph of minimum out-degree at least [Formula: see text] and [Formula: see text], respectively, contains the [Formula: see text]-subdivision of the in-star with [Formula: see text] leaves as a subgraph; this would be tight and generalizes a conjecture of Thomassé. We prove this for digraphs and [Formula: see text] up to a factor of less than 2.
No takes yet. Share an insight, caveat, or question.
Hons et al. (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: