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.