Counting Hamilton 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 Hamilton 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 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 Hamilton path, named after Hamilton, who
first described them.
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.)
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
Hamilton 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 Hamilton 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 Hamilton paths. For the above graph, there are 13,535,280 Hamilton 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 Hamilton 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 Hamilton Cycles
in P4 x Pn. Let H(n) be equal to the
number of Hamilton 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 Hamilton 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 Hamilton 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 an brute force algorithm
to calculate the characteristic polynomial.
After showing my results to Frits Göbel again, he sent me
an article by Harris Kwong, that dealt with the number of Hamilton 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:
This paper investigates the number of spanning subgraphs of the product
of an arbitrary graph G with the path graphs Pn on n vertices
that meet certain properties: connectivity, acyclicity, Hamiltonicity, and
restrictions on degree. A general method is presented for constructing a
recurrence equation R(n) for the graphs G x Pn,
giving the number of spanning subgraphs that satisfy a given combination of the
properties.
The primary result is that all constructed recurrence equations are
homogeneous linear recurrence equations with integer coefficients.
A second result is that the
property ``having a spanning tree with degree restricted to 1 and 3''
is a comparatively strong property,
just like the property ``having a Hamilton cycle'',
which has been studied extensively in literature.
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.
(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
Hamilton 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
seperate 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.
home page
