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
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?)

  • [1] A. Bell and P. Hallowell, Crawling round a cube edge, Computing (U.K.) (Feb. 1973), 9.
  • [2] Nicos Christofides, Graph theory: An algorithmic approach, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich Publishers], New York, 1975. MR 0429612 (55 #2623)
  • [3] Clay Culver and David Leach, Equivalence classes of 5-bit Gray codes, Australas. J. Combin. 39 (2007), 129-134. MR 2351193 (2008g:05008)
  • [4] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to algorithms, 3rd ed., MIT Press, Cambridge, MA, 2009. MR 2572804 (2010j:68001)
  • [5] Italo J. Dejter and Abel A. Delgado, Classes of Hamilton cycles in the 5-cube, J. Combin. Math. Combin. Comput. 61 (2007), 81-95. MR 2322204 (2008i:05109)
  • [6] M. Deza and R. Shklyar, Enumeration of Hamiltonian cycles in 6-cube, arXiv:1003.4391v1, 2010.
  • [7] Jiří Fink, Perfect matchings extend to Hamilton cycles in hypercubes, J. Combin. Theory Ser. B 97 (2007), no. 6, 1074-1076. MR 2354719 (2008g:05120),
  • [8] M. Gardner, Mathematical Games, Scientific American 227(2) (Aug. 1972), 106-109.
  • [9] Michael R. Garey and David S. Johnson, Computers and intractability, A guide to the theory of NP-completeness; A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. MR 519066 (80g:68056)
  • [10] E. N. Gilbert, Gray codes and paths on the $ n$-cube, Bell System Tech. J 37 (1958), 815-826. MR 0094273 (20 #792)
  • [11] Frank Harary, John P. Hayes, and Horng-Jyh Wu, A survey of the theory of hypercube graphs, Comput. Math. Appl. 15 (1988), no. 4, 277-289. MR 949280 (89i:05230),
  • [12] Alexander Hulpke, Petteri Kaski, and Patric R. J. Östergård, The number of Latin squares of order 11, Math. Comp. 80 (2011), no. 274, 1197-1219. MR 2772119 (2011m:05064),
  • [13] Petteri Kaski, Isomorph-free exhaustive generation of designs with prescribed groups of automorphisms, SIAM J. Discrete Math. 19 (2005), no. 3, 664-690 (electronic). MR 2191287 (2006h:05038),
  • [14] Petteri Kaski and Patric R. J. Östergård, Classification algorithms for codes and designs, Algorithms and Computation in Mathematics, vol. 15, Springer-Verlag, Berlin, 2006. With 1 DVD-ROM (Windows, Macintosh and UNIX). MR 2192256 (2008a:05002)
  • [15] P. Kaski and O. Pottonen, libexact user's guide, version 1.0, HIIT Technical Reports 2008-1, Helsinki Institute for Information Technology HIIT, 2008.
  • [16] Donald E. Knuth, The art of computer programming. Vol. 4, Fasc. 2, Generating all tuples and permutations, Addison-Wesley, Upper Saddle River, NJ, 2005. MR 2251595 (2007f:68004b)
  • [17] D. E. Knuth, The Art of Computer Programming, Volume 4A, Combinatorial Algorithms, Part 1, Addison-Wesley, Upper Saddle River, 2011. MR 0378456 (51:14624)
  • [18] Donald E. Knuth, Selected papers on fun & games, CSLI Lecture Notes, vol. 192, CSLI Publications, Stanford, CA, 2011. MR 2905906 (2012m:01013)
  • [19] William Kocay, An extension of the multi-path algorithm for finding Hamilton cycles, Discrete Math. 101 (1992), no. 1-3, 171-188. Special volume to mark the centennial of Julius Petersen's ``Die Theorie der regulären Graphs'', Part II. MR 1172376 (93g:05095),
  • [20] William Kocay and Donald L. Kreher, Graphs, algorithms, and optimization, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2005. MR 2106632 (2005k:05001)
  • [21] D. L. Kreher and D. R. Stinson, Combinatorial algorithms: Generation, enumeration, and search, CRC Press, Boca Raton, 1999.
  • [22] Martin Loebbing and Ingo Wegener, Comments on: ``The number of knight's tours equals 33,439,123,484,294--counting with binary decision diagrams'', Electron. J. Combin. 3 (1996), no. 1, Research Paper 5, Comment 1, 1 HTML document (electronic). MR 1715429
  • [23] S. Martello, Algorithm 595: An enumerative algorithm for finding Hamiltonian circuits in a directed graph, ACM Trans. Math. Software 9 (1983), 131-138.
  • [24] B. D. McKay, nauty user's guide (version 1.5), Technical Report TR-CS-90-02, Computer Science Department, Australian National University, Canberra, 1990.
  • [25] B. D. McKay, Knight's tours of an $ 8 \times 8$ chessboard, Technical Report TR-CS-97-03, Computer Science Department, Australian National University, Canberra, 1997.
  • [26] Brendan D. McKay, Isomorph-free exhaustive generation, J. Algorithms 26 (1998), no. 2, 306-324. MR 1606516 (98k:68132),
  • [27] Frank Rubin, A search procedure for Hamilton paths and circuits, J. Assoc. Comput. Mach. 21 (1974), 576-580. MR 0349480 (50 #1973)
  • [28] Jefferey A. Shufelt and Hans J. Berliner, Generating Hamiltonian circuits without backtracking from errors, Theoret. Comput. Sci. 132 (1994), no. 1-2, 347-375. MR 1290549 (95e:05067),
  • [29] Jerry Silverman, Virgil E. Vickers, and John L. Sampson, Statistical estimates of the $ n$-bit Gray codes by restricted random generation of permutations of 1 to 2$ ^{n}$, IEEE Trans. Inform. Theory 29 (1983), no. 6, 894-901. MR 733197 (85c:94030),
  • [30] Takeaki Uno, A fast algorithm for enumerating bipartite perfect matchings, Algorithms and computation (Christchurch, 2001) Lecture Notes in Comput. Sci., vol. 2223, Springer, Berlin, 2001, pp. 367-379. MR 1917757 (2003e:05130),
  • [31] Leslie G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput. 8 (1979), no. 3, 410-421. MR 539258 (80f:68055),
  • [32] B. Vandegriend, Finding Hamiltonian Cycles: Algorithms, Graphs and Performance, M.Sc. thesis, Department of Computing Science, University of Alberta, Edmonton, 1998.
  • [33] Douglas B. West, Introduction to graph theory, Prentice Hall Inc., Upper Saddle River, NJ, 1996. MR 1367739 (96i:05001)
  • [34] S. Winker to M. Gardner, 31 October 1972, Guide to the Martin Gardner Papers, Department of Special Collections, Stanford University Libraries, Stanford.

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

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.

American Mathematical Society