2012/02/13 by Hao Huang, Jie Ma, Huang, Hao +7 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1202.2602
openalex publication_date 2012/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A minimum feedback arc set of a directed graph G is a smallest set of arcs whose removal makes G acyclic. Its cardinality is denoted by β(G). We show that an Eulerian digraph with n vertices and m arcs has β(G) ≥ m2/2n2+m/2n, and this bound is optimal for infinitely many m, n. Using this result we prove that an Eulerian digraph contains a cycle of length at most 6n2/m, and has an Eulerian subgraph with minimum degree at least m2/24n3. Both estimates are tight up to a constant factor. Finally, motivated by a conjecture of Bollobás and Scott, we also show how to find long cycles in Eulerian digraphs.