2012/04/20 by Hao Liang, Liang, Hao, Jun‐Ming Xu +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1204.4516
arxiv created 2012/04/20 · openalex publication_date 2012/04/20 · arxiv updated 2012/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a simple digraph G, let β(G) be the size of the smallest subset X⊆ E(G) such that G-X has no directed cycles, and let γ(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)≤ (1)/(m-2)γ(G) for any m-free digraph G, which generalized some known results.