Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-063 | 2nd July 2007 00:00

Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations


Authors: Tomas Feder, Carlos Subi
Publication: 23rd July 2007 04:54
Downloads: 3055


We conjecture that for every perfect matching $M$ of the $d$-dimensional
$n$-vertex hypercube, $d\geq 2$, there exists a second perfect matching $M'$
such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the
$d$-dimensional hypercube. We prove this conjecture in the case where there are
two dimensions that do not get used by $M$. As a consequence, if $M_d$ is the
number of perfect matchings and $H_d$ is the number of Hamiltonian circuits of
the $d$-dimensional hypercube, then $M_{d-2}^4\leq H_d\leq M_d^2/4$.
By known bounds on the number of perfect matchings of the $d$-dimensional
hypercube that show $M_d={(\frac{d}{e}(1+o(1)))}^{n/2}$ and,
in particular, $M_d\leq {(d!)}^{n/(2d)}$ we infer that
${(\frac{d}{e}(1-o(1)))}^{n/2}\leq H_d
\leq {(d!)}^{n/(2d)}{((d-1)!)}^{n/(2(d-1))}/2$.
We finally strenthen this result to a nearly tight bound
${((d\log 2/(e\log\log d))(1-o(1)))}^n\leq H_d\leq {((d/e)(1+o(1)))}^n$.
We extend the results to graphs that are the Cartesian product of squares
and arbitrary bipartite regular graphs that have a Hamiltonian cycle.
We also study a labeling scheme related to matchings.

ISSN 1433-8092 | Imprint