http://openproblemgarden.org/op/minimal_graphs_with_a_prescribed_number_of_spanning_trees Comments for "Minimal graphs with a prescribed number of spanning trees" en http://openproblemgarden.org/op/minimal_graphs_with_a_prescribed_number_of_spanning_trees <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/azarija_jernej">Azarija</a>; <a href="/category/skrekovski">Skrekovski</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; Let <img class="teximage" src="/files/tex/03699c2971c6eb403dcc4c26a1c9818ad7b45da8.png" alt="$ n \geq 3 $" /> be an integer and let <img class="teximage" src="/files/tex/7cf5e54f55a113042ef4e18f16bdf6601a27462e.png" alt="$ \alpha(n) $" /> denote the least integer <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" /> such that there exists a simple graph on <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" /> vertices having precisely <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" /> spanning trees. Then <img class="teximage" src="/files/tex/196d4bae3ba249904f8319dc18b830afd9cc7fe8.png" alt="$ \alpha(n) = o(\log{n}). $" /> </div> </tr></td> </table> </td> </tr> </table> Azarija, Jernej Skrekovski, Riste number of spanning trees, asymptotics Graph Theory http://openproblemgarden.org/op/minimal_graphs_with_a_prescribed_number_of_spanning_trees#comment Sun, 22 Apr 2012 18:40:44 +0200 azi 37420 at http://openproblemgarden.org