Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 

 

Counting Hamiltonian cycles in bipartite graphs


Authors: Harri Haanpää and Patric R. J. Östergård
Journal: Math. Comp. 83 (2014), 979-995
MSC (2010): Primary 05C45, 05C85, 05C30, 05C38, 68R10
DOI: https://doi.org/10.1090/S0025-5718-2013-02741-X
Published electronically: July 15, 2013
MathSciNet review: 3143701
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A method for counting Hamiltonian cycles in bipartite graphs is developed with the main focus on the long-standing open case of the 6-cube. Dynamic programming as well as utilization of the automorphism group of the graph are central ingredients of the method. It is further shown how the number of equivalence classes of Hamiltonian cycles can be obtained via a classification of Hamiltonian cycles with nontrivial automorphisms. It turns out that the 6-cube has $ 35\,838\,213\,722\,570\,883\,870\,720$ Hamiltonian cycles and $ 777\,739\,016\,577\,752\,714$ equivalence classes of Hamiltonian cycles. The old result on the number of knight's tours on a $ 8\times 8$ chessboard is confirmed.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 05C45, 05C85, 05C30, 05C38, 68R10

Retrieve articles in all journals with MSC (2010): 05C45, 05C85, 05C30, 05C38, 68R10


Additional Information

Harri Haanpää
Affiliation: Department of Communications and Networking, Aalto University School of Electrical Engineering, P.O. Box 13000, 00076 Aalto, Finland

Patric R. J. Östergård
Affiliation: Department of Communications and Networking, Aalto University School of Electrical Engineering, P.O. Box 13000, 00076 Aalto, Finland

DOI: https://doi.org/10.1090/S0025-5718-2013-02741-X
Keywords: Bipartite graph, enumeration, Hamiltonian cycle, hypercube
Received by editor(s): November 7, 2011
Received by editor(s) in revised form: March 12, 2012, and June 25, 2012
Published electronically: July 15, 2013
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.