2025/12/01 by Jiangdong Ai, Gregory Gutin, Ai, Jiangdong +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2512.01676
openalex publication_date 2025/12/01 · openalex created_date 2025/12/03 · openalex updated_date 2026/07/28
A digraph D is an oriented graph if D does not have a pair of opposite arcs. The degree of a vertex v of D is the sum of the in-degree and out-degree of v. Let fvs(D) be the minimum number of vertices whose deletion from D makes it acyclic. Let D be a digraph with n vertices and maximum degree Δ. We prove the following bounds. If D is an oriented graph, then fvs(D)≤ (3n)/(7) when Δ≤ 4 and fvs(D)≤ (n)/(2) when Δ≤ 5. If D is a connected digraph, Δ≤ 4 and D is not obtained from an odd undirected cycle by replacing every edge with the pair of opposite arcs with the same endvertices, then fvs(D)≤ (n)/(2). If D is an arbitrary digraph with Δ≤ 5 then fvs(D)≤ (2n)/(3). Note that all the above bounds are tight.