__
TR08-087 | 31st July 2008 00:00
__

#### Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations (revised)

**Abstract:**
It has been shown that for every perfect matching $M$ of the $d$-dimensional

$n$-vertex hypercube, $d\geq 2, n=2^d$, 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 a generalization of a special case of this

result when there are two dimensions that do not get used by $M$.

It is known that the number $M_d$ of perfect matchings of the $d$-dimensional

hypercube satisfies $M_d={(\frac{d}{e}(1+o(1)))}^{n/2}$ and,

in particular, ${(2d/n)}^{n/2} (n/2)!\leq M_d\leq {(d!)}^{n/(2d)}$.

It has also been shown that the number $H_d$ of Hamiltonian circuits of the

hypercube satisfies

$1\leq \lim_{d\rightarrow\infty} (\log H_d)/(\log M_d)\leq 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!)}^{n/(2d)}{((d-1)!)}^{n/(2(d-1))}/2$

proving that $\lim_{d\rightarrow\infty} (\log H_d)/(\log M_d)=2$.

The proofs are based on a result for 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.