## Counting Hamiltonian cycles in bipartite graphs

HTML articles powered by AMS MathViewer

- by Harri Haanpää and Patric R. J. Östergård PDF
- Math. Comp.
**83**(2014), 979-995 Request permission

## 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

- A. Bell and P. Hallowell,
*Crawling round a cube edge*, Computing (U.K.) (Feb. 1973), 9. - Nicos Christofides,
*Graph theory*, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1975. An algorithmic approach. MR**0429612** - Clay Culver and David Leach,
*Equivalence classes of 5-bit Gray codes*, Australas. J. Combin.**39**(2007), 129–134. MR**2351193** - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein,
*Introduction to algorithms*, 3rd ed., MIT Press, Cambridge, MA, 2009. MR**2572804** - 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** - M. Deza and R. Shklyar, Enumeration of Hamiltonian cycles in 6-cube, arXiv:1003.4391v1, 2010.
- Jiří Fink,
*Perfect matchings extend to Hamilton cycles in hypercubes*, J. Combin. Theory Ser. B**97**(2007), no. 6, 1074–1076. MR**2354719**, DOI 10.1016/j.jctb.2007.02.007 - M. Gardner, Mathematical Games, Scientific American
**227**(2) (Aug. 1972), 106–109. - Michael R. Garey and David S. Johnson,
*Computers and intractability*, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR**519066** - E. N. Gilbert,
*Gray codes and paths on the $n$-cube*, Bell System Tech. J.**37**(1958), 815–826. MR**94273**, DOI 10.1002/j.1538-7305.1958.tb03887.x - 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**, DOI 10.1016/0898-1221(88)90213-1 - 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**, DOI 10.1090/S0025-5718-2010-02420-2 - Petteri Kaski,
*Isomorph-free exhaustive generation of designs with prescribed groups of automorphisms*, SIAM J. Discrete Math.**19**(2005), no. 3, 664–690. MR**2191287**, DOI 10.1137/S0895480104444788 - 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** - P. Kaski and O. Pottonen, libexact user’s guide, version 1.0, HIIT Technical Reports 2008-1, Helsinki Institute for Information Technology HIIT, 2008.
- Donald E. Knuth,
*The art of computer programming. Vol. 4, Fasc. 2*, Addison-Wesley, Upper Saddle River, NJ, 2005. Generating all tuples and permutations. MR**2251595** - Donald E. Knuth,
*The art of computer programming*, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR**0378456** - Donald E. Knuth,
*Selected papers on fun & games*, CSLI Lecture Notes, vol. 192, CSLI Publications, Stanford, CA, 2011. MR**2905906** - 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**, DOI 10.1016/0012-365X(92)90601-B - 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** - D. L. Kreher and D. R. Stinson,
*Combinatorial algorithms: Generation, enumeration, and search*, CRC Press, Boca Raton, 1999. - 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, approx. 4 pp. (electronic); 1 368 332]*, Electron. J. Combin.**3**(1996), no. 1, Research Paper 5, Comment 1, 1 HTML document. MR**1715429** - S. Martello, Algorithm 595: An enumerative algorithm for finding Hamiltonian circuits in a directed graph,
*ACM Trans. Math. Software***9**(1983), 131–138. - B. D. McKay,
*nauty*user’s guide (version 1.5), Technical Report TR-CS-90-02, Computer Science Department, Australian National University, Canberra, 1990. - 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.
- Brendan D. McKay,
*Isomorph-free exhaustive generation*, J. Algorithms**26**(1998), no. 2, 306–324. MR**1606516**, DOI 10.1006/jagm.1997.0898 - Frank Rubin,
*A search procedure for Hamilton paths and circuits*, J. Assoc. Comput. Mach.**21**(1974), 576–580. MR**349480**, DOI 10.1145/321850.321854 - 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**, DOI 10.1016/0304-3975(94)90239-9 - 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**, DOI 10.1109/TIT.1983.1056755 - 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**, DOI 10.1007/3-540-45678-3_{3}2 - Leslie G. Valiant,
*The complexity of enumeration and reliability problems*, SIAM J. Comput.**8**(1979), no. 3, 410–421. MR**539258**, DOI 10.1137/0208032 - B. Vandegriend,
*Finding Hamiltonian Cycles: Algorithms, Graphs and Performance*, M.Sc. thesis, Department of Computing Science, University of Alberta, Edmonton, 1998. - Douglas B. West,
*Introduction to graph theory*, Prentice Hall, Inc., Upper Saddle River, NJ, 1996. MR**1367739** - S. Winker to M. Gardner, 31 October 1972,
*Guide to the Martin Gardner Papers*, Department of Special Collections, Stanford University Libraries, Stanford.

## 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
- 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
- © Copyright 2013
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 3143701