Home » Keyword index

feedback edge set


Graph Theory » Directed Graphs

Non-edges vs. feedback edge sets in digraphs ★★★

Author(s): Chudnovsky; Seymour; Sullivan

For any simple digraph $ G $, we let $ \gamma(G) $ be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and $ \beta(G) $ be the size of the smallest feedback edge set.

Conjecture  If $ G $ is a simple digraph without directed cycles of length $ \le 3 $, then $ \beta(G) \le \frac{1}{2} \gamma(G) $.

Keywords: acyclic; digraph; feedback edge set; triangle free

Posted by mdevos
updated July 8th, 2008
add new comment
Syndicate content