Previous Up Next

Counting Hamiltonian cycles in product graphs

This is a subject that has intrigued me as long as I could write computer programs. I have always been interested by seemingly simple problems that result in complex answers. This subject interested me even before I knew it had a name. Actually, it all started with Hamiltonian paths.

The very beginning

It all started with a idea that I had, about a program that would draw a snake on the screen. The snake would start at one place in a box, and then extend itself until it could not go further, after which it would shrink again, to seek another path. A snap-shot of the screen could look like:
            *===============*
            #    +--+       #
            #    |  |       #
            #    +  +--+    #
            #    |     |    #
            # +--+  +--+    #
            # |     |       #
            # +-->  |       #
            *===============*

A Fortran program

A little later, I wrote a FORTRAN program, that would write down movements that the snake would make, for a certain problem. This would generate output like this:
nnnnwsssswnnnnwsssswnnnn
                  wnnn
                   se
                 wnn
                  ssen
                   esw
And so on for many pages...
(An n stands for going North, w for West, z for South, and e for East.) If you want to see it for yourself, here is a C program, which does the same thing.

I was amazed that such a simple program could generate so much complex output, in which repeating patterns can be recognized.

At the university

At the university I learned about graph theory. The box that I had in mind, could be represented by a graph, which could be constructed by taking the product of two line graphs. A box of three by five is equivalent of the product of the graphs P3 and P5, which looks like:
           *--*--*--*--*  P5
P3
     *     *--*--*--*--*
     |     |  |  |  |  |
     *     *--*--*--*--*
     |     |  |  |  |  |
     *     *--*--*--*--*
                          P3 x P5
I also learned that each snake that would visit all the points of the graph is called a Hamiltonian path, named after William Rowan Hamilton, who first described them.

On an Acorn Atom

When one of my room-mates got an Acorn Atom, I started writing programs that could draw the 'snakes', and later also programs that could count them. It was then that I discovered that counting them by brute force, took increasingly more time, as the number of points of the graphs increased. This forced me to use machine language. But also there, the limits where reached quickly. The largest graph that I tried was P7 x P7. The program took almost a complete day, to find the approximately 1.5 million paths, starting from the top right-hand corner. (Much later, I wrote an emulator for the Acorn Atom.)

Using PASCAL

When Turbo PASCAL became available, I started using it to write more advanced counting programs. First, I tried caching algorithms, with not much success. Later, I had more success with stronger cut-off rules, which would prevent the `snake' to make a wrong decision, when it was still short. These proved to be rather effective, and I could count the number of Hamiltonian paths in larger product graphs. The last program I wrote, was plain1.pas (converted to C: plain1.c). This program finds the 1,510,446 Hamiltonian paths starting from a corner in a P7 x P7, within a minute on a DX2. The program generated the following output:
   7   7   1   1     1510446 *            4 =      6041784
       0       0   20946       0   41669       0   88418
       0   24648       0   51964       0   88418       0
   20946       0   33696       0   52824       0   55868
       0   51964       0   64324       0   87368       0
   41669       0   52824       0   64060       0   62672
       0   88418       0   87368       0  111712       0
   88418       0   55868       0   62672       0  111712
(and more)

It was also at that time, that I tried to determine the total numbers of Hamiltonian paths. For the above graph, there are 13,535,280 Hamiltonian paths. See the file 7_7.txt for the number of paths between any two points (taking in symmetry axes in account), which is made by the program process.pas (or in C: process.c), that processes the output of the previous program.

But again, I quickly met the limits, because the number of paths increase exponentially with the number of points.

A report on Hamiltonian cycles

When I showed these results to Frits Göbel, my graph-theory teacher, he gave me a report with the title: `On the Number of Hamilton Cycles in Product Graphs' (Memorandum nr. 289, Department of Applied Mathematics, University of Twente, October 1979). In this report he gave a formula for the number of Hamiltonian Cycles in P4 x Pn. Let H(n) be equal to the number of Hamiltonian paths in P4 x Pn, then he found: H(1) = 0, H(2) = 1, H(3) = 2, H(4) = 6, H(5) = 14, and H(n) = 2H(n-1) + 2H(n-2) - 2H(n-3) + H(n-4) for all n larger than 5.

From the idea presented in this report, I developed a program (hamil.pas) that could calculate the number of Hamiltonian paths in Pm x Pn, for a given m and any n. Again, there were practical limits. The value of m could not be bigger then 5, due to memory limits. Also the maximum number of digits of the output numbers was fixed before hand.

Using C: a more general program

As I wanted to address the more general case of the product of any graph with Pn, and also be able to count Hamiltonian paths, 2-factors and other things, I wrote a new program (from scratch) using C.

Later, I heard that by finding the characteristic polynomial of the transition matrix (that my program constructed) a recurrence equation can be derived. So, I implemented a brute force algorithm to calculate the characteristic polynomial.

Writing a paper

After showing my results to Frits Göbel again, he sent me an article by Harris Kwong, that dealt with the number of Hamiltonian paths in P5 x Pn. This made me realize that my results went much further then that of others, and I decided to write a paper about my results.

During the writing of the paper I did some more work on my program, and found many more results. The paper was rejected, but I was encouraged to submit again, as the referee considered my results interesting.

Working on the paper again, gave me some new ideas for calculating the recurrence equation from the numbers that I found, by means of trying to solve it. I quickly found out that I needed whole numbers (Z) with arbitrary length. Implementing a set of efficient procedures for this took some time. And during the testing, I found many more results. This program can be found in count.c.

The paper that I refer has been published in `Ars Combinatoria', Volume XLIX, August 1998 under the title `On the number of specific spanning subgraphs of the graphs G x Pn'. From the abstract:

An earlier version of the paper, from which the results have been omitted, is available as zipped PostScript file or as PDF.

References to this paper are:

Rook paths on a chess board

Through some postings in sci.math I came across the problem related to the number of paths a rook could walk on a chess-board from one corner to the other without visiting a field more than once. This problem is (was) called the chess/rook.path problem in the rec.puzzle FAQ. I expanded my program again to include this problem. For more details see a page dedicated to this problem.

The Encyclopedia of Integer Sequences

When I found The Online Encyclopedia of Integer Sequences maintained by Neil Sloane, I submitted some sequences.

Rewriting the program

Because the variable names used by the program did not really fit the terminology used in the paper, I changed them in a new version of the program.

Spanning trees

When someone posted a question about the number of labyrinths, where a labyrinth is a rectangular maze where any two `squares' are connect by exactly one `path', of size n by m, Noam Elkies replied with some stunning facts.

Using Maple

(March 27, 1997) Two days ago, I happened to page through a book about Maple, and decided to give Maple a try again. Yesterday, I found the solution for the number of Hamiltonian Cycles in P8 x Pn.

Using Maple (cont'd)

Today, that is August 12, I checked the above result against the numbers found, and discovered that the equation is incorrect. The problem was that I generated the wrong matrix as input for Maple. I have corrected the problem, so the result is correct now.

Latest version

The latest version of count.c, including the interface with Maple, is available.

Results from counting program

The results from the counting program are presented on a separate page.

Richard Guy

On Tuesday, February 3, 2009, Richard Guy made some inquiries about some of the recurrence equations and I used the counting program to provide him with the terms of some sequence.

Robert Stoyan and Volker Strehl

On Tuesday, May 5, 2009, I received an email from Artem M. Karavaev informing me that he recently found a recurrence for the number of Hamilton cycles in P9xP2n based on the paper Enumeration of Hamiltonian Circuits in Rectangular Grids by Robert Stoyan and Volker Strehl. This paper was published in 1996 in Journal of Combinatorial Mathematics and Combinatorial Computing, which is actually two years before my own paper.

More results by Artem M. Karavaev

On Thursday, April 7, 2011, I received an email from Artem M. Karavaev informing me about many more results being published on a website. I have added these to results page.

Restrictions on component size

On Thursday, September 15, 2011, I realized that restrictions on the size of components is also an easy to implement restriction.

Program by

On Saturday, June 16, 2012, Anand Krishnamoorthi send me his program for counting Hamiltonian paths. More details.

The paper Untying The Gordian Knot via Experimental Mathematics (ArXiv) by Yukun Yao and Doron Zeilberger references to my paper. At end of section The human approach to enumerating spanning trees of gridgraphs the authors write: This is actually the method that I used for finding the recurrence equations before I knew one could calculate them from the characteristic polynomial.
home page