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

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

2012-02-13

arxiv.org/abs/1202.2602v1

Mathematics

Combinatorics

Scientific paper

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 $\beta(G)$. We show that an Eulerian digraph with $n$ vertices and $m$ arcs has $\beta(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\'as and Scott, we also show how to find long cycles in Eulerian digraphs.

Affiliated with

Also associated with

No associations

Rating

Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-680807