Minimum feedback arc set of m-free digraphs

For a simple digraph G  , let β(G)β(G) be the size of the smallest subset X⊆E(G)X⊆E(G) such that G−XG−X has no directed cycles, and let γ(G)γ(G) be the number of unordered pairs of nonadjacent vertices in G. A digraph G is called m-free if G has no directed cycles of length at most m  . This paper proves that β(G)⩽1m−2γ(G) for any m-free digraph G, which generalizes some known results.

► G is a digraph without directed cycles of length at most m  .
► β(G)β(G) denotes the feedback edge-number of G  .
► γ(G)γ(G) denotes the number of unordered pairs of nonadjacent vertices in G  .
► We prove that β(G)⩽1m−2γ(G).
► This result generalizes some known results.