*===============* # +--+ # # | | # # + +--+ # # | | # # +--+ +--+ # # | | # # +--> | # *===============*

nnnnwsssswnnnnwsssswnnnn wnnn se wnn ssen eswAnd so on for many pages...

(An

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

*--*--*--*--* PI 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._{5}P_{3}* *--*--*--*--* | | | | | | * *--*--*--*--* | | | | | | * *--*--*--*--* P_{3}x P_{5}

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.

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.

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.

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:

- The number of spanning trees in graphs with a given degree sequence by Alexandr V. Kostochka gives upper and lower limits for the number of spanning degrees for a given degree sequence.

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.

References to this paper are:

- Domino Tilings and Products of Fibinacci and Pell Numbers by James A. Sellers.

home page