Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with n-cube:
TR07-063 | 2nd July 2007
Tomas Feder, Carlos Subi

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

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 ... more >>>

ISSN 1433-8092 | Imprint