RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretn. Anal. Issled. Oper., Ser. 1, 2001, Volume 8, Number 2, Pages 52–62 (Mi da220)  

This article is cited in 6 scientific papers (total in 6 papers)

On the number of Hamiltonian cycles in a Boolean cube

A. L. Perezhogin, V. N. Potapov

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: We show that as $n\to\infty$ the logarithm of the number of partitions of an $n$-dimensional Boolean cube $E^n$ into cycles is equal to $2^n(\ln n-1+o(1))$ and the logarithm of the number of Hamiltonian cycles in $E^n$ is at least $2^{n-1}(\ln n-1+o(1))$. We prove that each perfect matching in $E^n$ in which the edges have at most $k$ directions can be complemented to a Hamiltonian cycle for any $n\geqslant n_0(k)$.

Full text: PDF file (932 kB)

Bibliographic databases:
UDC: 519.172
Received: 06.02.2001

Citation: A. L. Perezhogin, V. N. Potapov, “On the number of Hamiltonian cycles in a Boolean cube”, Diskretn. Anal. Issled. Oper., Ser. 1, 8:2 (2001), 52–62

Citation in format AMSBIB
\Bibitem{PerPot01}
\by A.~L.~Perezhogin, V.~N.~Potapov
\paper On the number of Hamiltonian cycles in a~Boolean cube
\jour Diskretn. Anal. Issled. Oper., Ser.~1
\yr 2001
\vol 8
\issue 2
\pages 52--62
\mathnet{http://mi.mathnet.ru/da220}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1859856}
\zmath{https://zbmath.org/?q=an:0995.05087}


Linking options:
  • http://mi.mathnet.ru/eng/da220
  • http://mi.mathnet.ru/eng/da/v8/s1/i2/p52

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. L. Perezhogin, “O spetsialnykh sovershennykh parosochetaniyakh v bulevom kube”, Diskretn. analiz i issled. oper., ser. 1, ser. 1, 12:4 (2005), 51–59  mathnet  mathscinet  zmath
    2. A. D. Korshunov, “Some unsolved problems in discrete mathematics and mathematical cybernetics”, Russian Math. Surveys, 64:5 (2009), 787–803  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib
    3. Feder T., Subi C., “Nearly tight bounds on the number of Hamiltonian circuits of the hypercube and generalizations”, Inform Process Lett, 109:5 (2009), 267–272  crossref  mathscinet  zmath  isi  scopus
    4. V. N. Potapov, “Clique matchings in the $k$-ary $n$-dimensional cube”, Siberian Math. J., 52:2 (2011), 303–310  mathnet  crossref  mathscinet  isi
    5. V. N. Potapov, “Construction of Hamiltonian cycles with a given range of directions of edges in the Boolean $n$-dimensional cube”, J. Appl. Industr. Math., 6:3 (2012), 339–345  mathnet  crossref  mathscinet
    6. I. S. Bykov, “$2$-Factors without close edges in the $n$-dimensional cube”, J. Appl. Industr. Math., 13:3 (2019), 405–417  mathnet  crossref  crossref
  • Дискретный анализ и исследование операций
    Number of views:
    This page:403
    Full text:113

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020