http://openproblemgarden.org/op/non_edges_vs_feedback_edge_sets_in_digraphs Comments for "Non-edges vs. feedback edge sets in digraphs" en http://openproblemgarden.org/op/non_edges_vs_feedback_edge_sets_in_digraphs <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/chudnovsky_maria">Chudnovsky</a>; <a href="/category/seymour">Seymour</a>; <a href="/category/sullivan_blair">Sullivan</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/directed_graphs">Directed Graphs</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>For any simple digraph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />, we let <img class="teximage" src="/files/tex/a21b55c26aa5b9e5ed7584c1d99c4d415400a618.png" alt="$ \gamma(G) $" /> be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and <img class="teximage" src="/files/tex/fc20b3753b4717a47d73a243f9672517c37bade5.png" alt="$ \beta(G) $" /> be the size of the smallest <a href="http://en.wikipedia.org/wiki/feedback arc set">feedback edge set</a>. </p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp;If <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is a simple digraph without directed cycles of length <img class="teximage" src="/files/tex/2dbc994c29a8272f2fa20bee6216f47315c47aa7.png" alt="$ \le 3 $" />, then <img class="teximage" src="/files/tex/d2838535a0339a448fba3bbbab8586020be5f886.png" alt="$ \beta(G) \le \frac{1}{2} \gamma(G) $" />. </div> </tr></td> </table> </td> </tr> </table> Chudnovsky, Maria Seymour, Paul D. Sullivan, Blair acyclic digraph feedback edge set triangle free Graph Theory Directed Graphs http://openproblemgarden.org/op/non_edges_vs_feedback_edge_sets_in_digraphs#comment Tue, 08 Jul 2008 19:59:04 +0200 mdevos 1793 at http://openproblemgarden.org