pipette
ENEnglish

On the Number of Hamiltonian Cycles in a Boolean Cube

A.L.Perezhogin, V.N.Potapov

Preprint con versión publicada

En palabras de los autores

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 .

Resultado principalLimitación que admiten los autores

Apareció: viernes, 9 de octubre. arXiv. Preprint con versión publicada.

Versión publicada: Diskretn. Anal. Issled. Oper., Ser. 1, 8:2 (2001), 52-62

Comentario de los autores: 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