Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > HAMILTONIAN CIRCUIT:
Reports tagged with hamiltonian circuit:
TR08-087 | 31st July 2008
Tomas Feder, Carlos Subi

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

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




ISSN 1433-8092 | Imprint