On Sullivan’s conjecture on cycles in 4-free and 5-free digraphs

Research paper by Hao Liang, Jun Ming Xu

Indexed on: 20 Sep '12Published on: 20 Sep '12Published in: Acta Mathematica Sinica, English Series


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 k-free if G has no directed cycles of length at most k. This paper proves that β(G) ≤ 0.3819γ(G) if G is a 4-free digraph, and β(G) ≤ 0.2679γ(G) if G is a 5-free digraph. These improve the results of Sullivan in 2008.