pipette
ESEspañol

On the Number of Hamiltonian Cycles in a Boolean Cube

A.L.Perezhogin, V.N.Potapov

Preprint with a published version

In the authors' words

It is shown that, as , the logarithm of the number of decompositions into cycles of the -dimensional Boolean cube is \[ 2^n(\ln n-1+o(1)), \] and the logarithm of the number of Hamiltonian cycles in is at least \[ 2^{n-1}(\ln n-1+o(1)). \] It is proved that, in , every perfect matching whose edges belong to at most directions can be extended to a Hamiltonian cycle for every .

Main resultLimitation the authors admit

Appeared: Friday, October 9. arXiv. Preprint with a published version.

Published version: Diskretn. Anal. Issled. Oper., Ser. 1, 8:2 (2001), 52-62

Authors' comment: This article was published in Russian in 2001. The results of this article have been surpassed by the following papers. 1.Feder T., Subi C., Nearly tight bounds on the number of Hamiltonian circuits... Inf. Process. Lett. 109, No. 5, 267-27