2025/09/22 by J. G. Lu, Yaojun Chen, Lu, Junying +1
Computer Science · Mathematics · #05C20 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2509.17756
openalex publication_date 2025/09/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The girth of a graph G is the length of a shortest cycle of G. Jiang (JCT-B, 2001) showed that every graph G with girth at least 2ℓ+1 and minimum degree at least k/ℓ contains every tree T with k edges whose maximum degree does not exceed the minimum degree of G. Let δ0(D) be the minimum semidegree of a digraph D and Δ(D) be the maximum degree of D. In this paper, we establish a digraph version of Jiang's result, stating that every oriented graph D of girth at least 2ℓ+1 with δ0(D)≥ max\k/ℓ,Δ(T)\ contains every oriented tree with k edges, that answers a question raised by Stein and Trujillo-Negrete in affirmative.