Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs

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) \ge m^2/2n^2+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 $6n^2/m$, and has an Eulerian subgraph with minimum degree at least $m^2/24n^3$. 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.

No reviews yet.

No comments yet.