http://openproblemgarden.org/op/decomposing_a_connected_graph_into_paths Comments for "Decomposing a connected graph into paths." en http://openproblemgarden.org/op/decomposing_a_connected_graph_into_paths <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/gallai_tibor">Gallai</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/basic_graph_theory">Basic G.T.</a> » <a href="/category/paths_0">Paths</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; Every simple connected graph on <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" /> vertices can be decomposed into at most <img class="teximage" src="/files/tex/e116c3c13c7f23534b92d3065799149556b9055b.png" alt="$ \frac{1}{2}(n+1) $" /> paths. </div> </tr></td> </table> </td> </tr> </table> Gallai, Tibor Graph Theory Basic Graph Theory Paths http://openproblemgarden.org/op/decomposing_a_connected_graph_into_paths#comment Mon, 04 Mar 2013 02:14:17 +0100 fhavet 46583 at http://openproblemgarden.org