http://openproblemgarden.org/op/total_domination_number_of_a_hypercube Comments for "Total Domination number of a hypercube" en http://openproblemgarden.org/op/total_domination_number_of_a_hypercube#comment-74276 <p>The conjecture is false and it can be seen that this is so by using a computer program. For example <img class="teximage" src="/files/tex/e619a7c90b6a162442dc380d8607147eeb40df98.png" alt="$ \gamma_t(Q_6) = 14 $" /> which is not a power of two.</p> <p>Alternatively we can argue as follows. For any graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> we clearly have <img class="teximage" src="/files/tex/6a5c921b246097b150425530d4dae16aca84e157.png" alt="$$ \gamma_t(G) \leq 2 \gamma(G).$$" /> Now the bound by Alon and Spencer states <img class="teximage" src="/files/tex/1250dda3df93b272a0d6c24fb71cde08bbbf2183.png" alt="$$\gamma(G) \leq \frac{1+\log({\delta(G)+1)}}{1+\delta(G)}|V(G)|.$$" /> In particular this implies that for any constant <img class="teximage" src="/files/tex/1e68311a7b4da4e3c617355583e845948b2a20b0.png" alt="$ k &gt; 0 $" /> and large enough <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" /> we have <img class="teximage" src="/files/tex/099ff5bee18c9a933295b14942b920abf5cc4ca8.png" alt="$$\gamma_t(Q_n) \leq 2^{n-k}.$$" /> </p> Sat, 30 Nov 2013 08:54:59 +0100 azi comment 74276 at http://openproblemgarden.org http://openproblemgarden.org/op/total_domination_number_of_a_hypercube <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/adel_p_kazemi">Adel P. Kazemi</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>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; For any integer <img class="teximage" src="/files/tex/5b3132d49e9fdff046189036c1228b4ad60b9f64.png" alt="$ n\geq 6 $" />, <img class="teximage" src="/files/tex/5983622a21cf9a1f3682fd1ddf6aa5e817779c43.png" alt="$ \gamma_t(Q_n) = 2^{n-2} $" />. </div> </tr></td> </table> </td> </tr> </table> Adel P. Kazemi Total domination number, Hypercube Graph Theory Basic Graph Theory http://openproblemgarden.org/op/total_domination_number_of_a_hypercube#comment Sun, 06 Oct 2013 16:27:35 +0200 Adel P. Kazemi 57904 at http://openproblemgarden.org