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 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
P_{3} and P_{5}, which looks like:
*--*--*--*--* P_{5}
P_{3}
* *--*--*--*--*
| | | | | |
* *--*--*--*--*
| | | | | |
* *--*--*--*--*
P_{3} x P_{5}
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.
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
P_{7} x P_{7}.
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
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 P_{7} x P_{7}, 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 P_{4} x P_{n}. Let H(n) be equal to the
number of Hamiltonian paths in P_{4} x P_{n},
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
P_{m} x P_{n},
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 P_{n}, 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.
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
P_{5} x P_{n}. 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 P_{n}'. From the abstract:
This paper investigates the number of spanning subgraphs of the product
of an arbitrary graph G with the path graphs P_{n} 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 P_{n},
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 Hamiltonian 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
Hamiltonian Cycles in P_{8} x P_{n}.
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.
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 P_{9}xP_{2n} 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:
Rather than think so hard, let's compute sufficiently many terms of
the enumera-tion sequence, and try to guess a linear recurrence equation
with constant coefficients
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