Destroying cycles in digraphs

作者：Dunkum Molly^*; Hamburger Peter; Por Attila

来源：Combinatorica, 2011, 31(1): 55-66.

DOI：10.1007/s00493-011-2589-4

For a simple directed graph G with no directed triangles, let beta(G) be the size of the smallest subset X a E(G) such that G\X has no directed cycles, and let gamma(G) denote the number of unordered pairs of nonadjacent vertices in G. Chudnovsky, Seymour, and Sullivan showed that beta(G) a parts per thousand currency sign gamma(G), and conjectured that beta(G) <= gamma(G), and conjectured that beta(G) <= gamma(G)/2. In this paper we prove that beta(G) < 0.88 gamma(G).

• 出版日期2011-1