The Number of Hamiltonian Paths in a Rectangular Grid

Karen L. Collins Lucia B. Krompart Dept. of Mathematics 243 W. Tienken Road Wesleyan University Rochester, MI 48306 Middletown, CT 06459-0128 lkrompar@oakland.edu kcollins@wesleyan.edu

Abstract It is easy to find out which rectangular m vertex by n vertex grids have a Hamiltonian path from one corner to another using a checkerboard argument. However, it is quite difficult in general to count the total number of such paths. In this paper we give generating function answers for grids with fixed m for m = 1, 2, 3, 4, 5.

1 Introduction

Given a grid with m vertices in each column and n vertices in each row, so that there are a total of mn vertices, how many Hamiltonian paths are there from the lower left corner (LL) to the upper right corner(UR)? For m = 1, the answer is 1 for any value of n. For m = 2, the answer is 0 if n is even and 1 if n is odd. If we fix m = 3 then the answer is surprisingly 2^{n−2}. Similarly, the number of Hamiltonian paths from the LL corner to the lower right corner (LR) of an m by n grid is 1 for m = 1; 0 if n is odd and 1 if n is even for m = 2; and 2^{n−2} for m = 3, and n > 0. The answers for the same questions when m = 4, 5 cannot be expressed so simply. Let f(m, n) be the number of Hamiltonian paths from the LL to the UR corner. For m = 4, 5, we provide a generating function which is the quotient of two polynomials, and contains the sequence f(m, 1), f(m, 2), f(m, 3), f(m, 4), … as the coefficients in its Taylor series expansion about 0.

We conjecture that a Hamiltonian path from LL to UR divides the squares of the grid into two sets of equal size, see Conjecture 3.

Rectangular grid graphs first appeared in [8]. The problem of the existence of a Hamiltonian path from any vertex in the grid to any other vertex (or of a Hamiltonian circuit) is studied by Itai et al. in [5]. Given a rectangular grid and two vertices, Itai et al. give necessary and sufficient conditions for the graph to have a Hamiltonian path between the two vertices. They also show that the general problem for nonrectangular grids is NP-complete. Everett [2] describes an O(n) algorithm for finding Hamiltonian paths in a large class of nonrectangular grids. In related work, Niederhausen [9] gives recurrence relations for the number of paths in R^{2} from the origin to (n, m) which pass through at least l points from a fixed lattice.

More progress has been made on the problem of enumerating Hamiltonian cycles in grids. Myers [10] proposed an algorithm for counting the number of Hamiltonian cycles of a specific size rectangular grid. Göbel [4] gives the correct number of Hamiltonian cycles for a 3 × n grid and the denominator of the generating function for the 4 × n grid. This paper also provides upper and lower asymptotic bounds for the number of Hamiltonian cycles in the m × n grid.

The problem is studied further by Kwong et al. in [13] and [7], and independently by Kreweras [6]. These papers find the generating functions for the total number of Hamiltonian cycles in a 4 × n and a 5 × n grid. This work has been extended by Stoyan, who has shown that the number of Hamiltonian cycles in an m × n grid for fixed m is a rational generating function, and computed these generating functions for m ≤ 7 [12]. We adapt the notation from [13, 7] for representing a Hamiltonian cycle as a sequence of digits.

C. Zamfirescu and T. Zamfirescu [14] find sufficient conditions for a nonrectangular grid graph to have a Hamiltonian cycle.

2 Describing paths in grids

Define a checkerboard coloring of an m × n grid as a bipartite coloring of the vertices of the grid in which the LL corner is colored black, its neighbors white, etc. Clearly a Hamiltonian path in a grid must alternate in vertex colors. If mn is odd, the end vertices must be the same color, and if mn is even, they must be different colors. On the other hand, if the LL vertex is black, then if n is even, the LR vertex will be white, and if n is odd the LR vertex will be black. If m + n − 1 is even, the UR vertex will be white, and if m + n − 1 is odd, the UR vertex will be black. This argument eliminates any Hamiltonian paths from the LL to the LR corners when m is even and n is odd, and any Hamiltonian paths from the LL to the UR corners when m is even and n is even. It is easy to check that in all other cases there is at least one Hamiltonian path from one corner to the other.

We follow the notation of Kwong et al., [7, 13], for describing a Hamiltonian cycle in a grid as a sequence of integers. In order to consider our Hamiltonian path as a cycle, we add an edge along the bottom of each grid to make a cycle. This cycle then has an an inside and an outside by the Jordan curve theorem. Each square of the grid can be labeled with 0 if it is outside the cycle, and 1 if it is inside. We also label the region underneath the grid enclosed by the extra edge between corner vertices with a 1. Call this the oval region. The infinite region is labeled with a 0. The edges of the grid used in the Hamiltonian cycle are exactly those edges which have a square or region labeled 1 on one side, and a square or region labeled 0 on the other.

Each column of squares is an m−1 digit number expressed in binary, with the bottom square having place value 2^{0} and the top square 2^{m−2}. Listing the values of the columns from left to right, we obtain a sequence with which we represent the Hamiltonian path. The Hamiltonian path in Figure 1 (A) is represented by the sequence 2, 3, 0, 2, 2 and in Figure 1 (B) by the sequence 3, 0, 3, 2, 2.

[figure: 1; 1; 0; 0; 0; 1; 1; 1; 0; 0; 0; 1; 0; 1; 1; 1; 0; 0; 1; 1; 0; 1; 0; 1; Figure 1; (A); (B)]

Every vertex in a Hamiltonian path must have degree 2 except for the two ends which have degree 1 inside the grid, with 1 added for the extra edge. The top square in the first column of a grid must be labeled with a 1, because the upper left corner vertex has degree two, and any Hamiltonian path must use both of its edges. This separates the top square from the outside region of zeroes. Also this square cannot be surrounded by squares labeled 0 inside the grid, or it will be separated from the oval region labeled 1.

Figure 2 shows patterns which are forbidden inside the grid because they would force the center vertex to have degree 4 or degree 0:

0 0 0 0  1 1 1 1  1 0 0 1  0 1 1 0 Figure 2 (A)  (B)  (C)  (D)

Similarly, adjacent squares on the border of the grid are forbidden to both be 0 if both are adjacent to the infinite region, and are forbidden to both be 1 if both are adjacent to the oval region, since the vertex on the outside of the grid in between the squares will have zero degree, see Figure 3. In particular the first column of a grid cannot contain consecutive squares labeled with 0.

0 0 0  1 1 1 (E)  (F) Figure 3

3 Recurrences that get us the generating functions

Theorem 1 Let n > 1. Then the 3 × n grid has 2^{n−2} Hamiltonian paths from its LL corner to its UR corner and from its LL corner to its LR corner.

Proof Let f(m, n) be the number of Hamiltonian paths from the LL corner to the UR corner of an m×n grid and g(m, n) be the number of Hamiltonian paths from the LL corner to the LR corner of an m×n grid. Then f(3, 1) = 1 and g(3, 1) = 0.

Consider the first column which is composed of two squares. The top square in each case must be labeled with a 1. Then the bottom square can be labeled either 0 or 1. It is now clear which edges in the first column belong to the Hamiltonian path. See Figure 4. Then for n > 1, f(3, n) = g(3, n − 1) + f(3, n − 1) and g(3, n) = f(3, n − 1) + g(3, n − 1), where the first term in each sum corresponds to the bottom square being 1, and the second to its being 0.

Let F (3, x) = ∑_{n=1}^{∞} f(3, n)x^{n} and G(3, x) = ∑_{n=1}^{∞} g(3, n)x^{n}. Then using the above recurrences and initial values, we get the two equations F (3, x) = xG(3, x) + xF (3, x) + x and G(3, x) = xF (3, x) + xG(3, x). We solve for F (3, x) and G(3, x) as variables and get that (1 − 2x)F (3, x) = x(1 − x) and (1 − 2x)G(3, x) = x^{2}. Expanding out the denominators of the generating functions x(1−x)/(1−2x) and x^{2}/(1−2x) using Newton’s binomial theorem shows that f(3, n) = g(3, n) = 2^{n−2} except when n = 1. □

[figure: 0; 1; 1; 1; Figure 4; (G); (H)]

Let q(x) = x^{8} − 7x^{6} + 9x^{4} − 7x^{2} + 1. Let F (4, x) = ∑_{n=1}^{∞} f(4, n)x^{n} and G(4, x) = ∑_{n=1}^{∞} g(4, n)x^{n}.

Theorem 2 q(x)F (4, x) = x(x^{4} − 3x^{2} + 1) and q(x)G(4, x) = x^{2}(x^{2} + 1)

Proof The top square in the first column of the 4 × n grid must again be labeled with 1. Thus the binary representation of the first column is 7, 6, 5, or 4. The lower two squares cannot both be zero, hence the first digit cannot be 4.

If the first digit is 5, the top square in the second column must be labeled 1 so that the top square in the first column is not separated from the rest of the regions labeled 1. The bottom square in the second column must be labeled 0 to avoid pattern F in Figure 3. The middle square must therefore be labeled 0 to avoid pattern C of Figure 2. Thus the second digit in the binary representation must be 4. The number of ways to fill out this path is f(4, n − 2) for LL corner to UR corner and g(4, n − 2) for LL corner to LR corner.

If the first digit is 7, then the number of ways to fill out this path is g(4, n − 1) for LL corner to UR corner and f(4, n − 1) for LL corner to LR corner.

We use two extra functions to get the recurrences. Let f_{6}(4, n) (g_{6}(4, n)) to be the number of Hamiltonian paths in an m × n grid from the LL corner to the UR corner (LR corner) where the first column is represented by 6.

Then if the first digit of the path is 6, the second digit can be 2, 3, or 4. The other possibilities can be eliminated by Figure 2, and the fact that the top square in the first column labeled 1 may not be separated from the rest of the regions labeled 1.

If the first two digits are 6,4 then the number of ways to fill out the rest of the path is f(4, n − 2) for the LL corner to the UR corner and g(4, n − 2) for the LL corner to the LR corner.

If the first two digits are 6,3 then the third must be 6. The number of ways to fill out the rest of the path is g(4, n − 3) for the LL corner to the UR corner and f(4, n − 3) for the LL corner to the LR corner.

If the first two digits are 6,2 then the third digit must be 7 or 6. The number of ways to fill out 6,2,7 is g(4, n − 3) for the LL corner to the UR corner and f(4, n − 3) for the LL corner to the LR corner. The number of ways to fill out 6,2,6 is f_{6}(4, n − 2) for the LL corner to the UR corner and g_{6}(4, n − 2) for the LL corner to the LR corner.

This gives us the following recursions: f(4, n) = f(4, n−2)+g(4, n−1)+ f_{6}(4, n); g(4, n) = g(4, n − 2) + f(4, n − 1) + g_{6}(4, n); f_{6}(4, n) = f(4, n − 2) + 2g(4, n−3)+f_{6}(4, n−2); and g_{6}(4, n) = g(4, n−2)+2f(4, n−3)+g_{6}(4, n−2).

Let F_{6}(4, x) = ∑_{n=1}^{∞} f_{6}(4, n)x^{n} and G_{6}(4, x) = ∑_{n=1}^{∞} g_{6}(4, n)x^{n}. Then using initial values f(4, 1) = g(4, 2) = 1 and g(4, 1) = f(4, 2) = 0 with f_{6}(4, 2) = g_{6}(4, 2) = g_{6}(4, 3) = 0 and f_{6}(4, 3) = 2,

F (4, x) = x^{2}F (4, x) + xG(4, x) + F_{6}(4, x) + x
G(4, x) = x^{2}G(4, x) + xF (4, x) + G_{6}(4, x)
F_{6}(4, x) = x^{2}F (4, x) + 2x^{3}G(4, x) + x^{2}F_{6}(4, x) + x^{3}
G_{6}(4, x) = x^{2}G(4, x) + 2x^{3}F (4, x) + x^{2}G_{6}(4, x)

We rewrite this as a matrix.

[ \begin{matrix}x^{2} − 1 & x & 1 & 0 \\ x & x^{2} − 1 & 0 & 1 \\ x^{2} & 2x^{3} & x^{2} − 1 & 0 \\ 2x^{3} & x^{2} & 0 & x^{2} − 1 \end{matrix} ] [ \begin{matrix}F (4, x) \\ G(4, x) \\ F_{6}(4, x) \\ G_{6}(4, x) \end{matrix} ] = [ \begin{matrix}−x \\ 0 \\ −x^{3} \\ 0 \end{matrix} ]

The determinant of the matrix is q(x). We solve for F (4, x), G(4, x), F_{6}(4, x), G_{6}(4, x) by finding the inverse of the matrix and multiplying it by the column vector [−x, 0, −x^{3}, 0]. We get the stated results for F (4, x) and G(4, x) plus q(x)F_{6}(4, x) = −(x^{9} − 6x^{7} + 6x^{5} − 2x^{3}) and q(x)G_{6}(4, x) = −(2x^{6} − 3x^{4}). □

Let p(x) = x^{12} +2x^{11} +5x^{10} +18x^{9} −24x^{8} +10x^{7} +30x^{6} −46x^{5} +2x^{4} +28x^{3} − 7x^{2}−4x+1. Let r(x) = x(x^{10}+x^{8}+4x^{7}−10x^{6}+2x^{5}−2x^{4}+9x^{3}−3x^{2}−3x+1) and s(x) = x^{2}(−6x^{7} + 5x^{6} + 6x^{4} − 6x^{3} + 1). Let F (5, x) = ∑_{n=1}^{∞} f(5, n)x^{n} and G(5, x) = ∑_{n=1}^{∞} g(5, n)x^{n}.

Theorem 3 p(x)F (5, x) = r(x) and p(x)G(5, x) = s(x)

Proof We consider the 5 × n grid. The top square in the first column must again be labeled with 1. No two consecutive squares in the first column can both be zero. Thus the first column can be represented by 10, 11, 13, 14 or 15. Let f_{2}(5, n) (g_{2}(5, n)) be the number of Hamiltonian paths that start at the LL corner and end at the UR (LR) corner that begin with the first column labeled 10, 11, 14, or 15. Each of 10, 11, 14 and 15 has 2 in its binary expansion. Let f_{4}(5, n) (g_{4}(5, n)) be the number of Hamiltonian paths that start at the LL corner and end at the UR (LR) corner that begin with the first column 13, 14, or 15. Each of 13, 14, and 15 has 4 in its binary expansion. Let f_{14,\overline{4}}(5, n) (g_{14,\overline{4}}(5, n)) be the number of Hamiltonian paths that start at the LL corner and end at the UR (LR) corner that begin with the first column represented by 14 AND there is no 4 in the binary expansion of the second column. Let h(5, n) be the number of Hamiltonian paths that start at the center vertex of the leftmost column of vertices in the grid and end at UR corner.

For each of the 9 functions we give a recurrence involving the same functions. We use the initial values given in the table.

f f_{2} f_{4} f_{14,\overline{4}} g g_{2} g_{4} g_{14,\overline{4}} h
n=1 1 1 1 0 0 0 0 0 0
n=2 1 1 0 0 1 1 1 0 1
n=3 8 6 6 2 4 4 2 1 3
n=4 20 19 11 6 23 21 16 5 15

1. f(5, n) = f_{2}(5, n)+f_{4}(5, n−2)+f(5, n−2) The only paths not counted in f_{2}(5, n) are the ones that start with 13. Using the previously discussed rules we can eliminate all but 8 or 4 for the label of the second column. If we begin 13,8 then the rest of the path can be filled out in f(5, n−2) ways. If we begin 13,4 then the rest of the path can be filled out in f_{4}(5, n − 2) ways. Replacing f by g and g by f in the above gives the recurrence for g(5, n).

2. f_{2}(5, n) = f_{14,\overline{4}}(5, n)+f_{2}(5, n−1)+g(5, n−1)+h(5, n−1)+f_{4}(5, n−2) The first column can be labeled 10, 11, 14, or 15. If it is 10, then the path can be filled out in f_{2}(5, n − 1) ways. If it is 11, then the path can be filled out in h(5, n − 1) ways. If it is 14, then it can be filled out in f_{14,\overline{4}}(5, n) ways if the second column has no 4 in its binary expansion. If there is a 4 in the binary expansion then the second column must be labeled 4. The remaining ways to finish the path are f_{4}(5, n − 2). If it is 15, then the path can be filled out in g(5, n − 1) ways. Replacing f by g and g by f in the above gives the recurrence for g_{2}(5, n).

3. f_{4}(5, n) = f_{14,\overline{4}}(5, n) + g(5, n − 1) + f(5, n − 2) + 2f_{4}(5, n − 2) The first column can be labeled 13, 14, or 15. If it is 13, the second column can be either 4 or 8. We get f_{4}(5, n − 2) from 13,4 and f(5, n − 2) from 13,8. If it is 14, then either the second column has a 4 in its binary expansion, or it does not. If it does not, we get f_{14,\overline{4}}(5, n) and if it does, then the second column must be labeled 4 and we get f_{4}(5, n − 2). If the first column is 15, then we get g(5, n − 1). Replacing f by g and g by f in the above gives the recurrence for g_{4}(5, n).

4. f_{14,\overline{4}}(5, n) = f_{14,\overline{4}}(5, n − 1) + f(5, n − 2) + f_{2}(5, n − 2) + g_{2}(5, n − 2) + h(5, n − 2) The second column can be labeled 2, 3, 8, 10, or 11. If it is 2, then we get f_{2}(5, n − 2). If it is 3, then we get h(5, n − 2). If it is 8, then we get f(5, n − 2). If it is 10, then we get f_{14,\overline{4}}(5, n − 1). If it is 11, then we get g_{2}(5, n − 2). Replacing f by g and g by f in the above gives the recurrence for g_{14,\overline{4}}(5, n).

5. h(5, n) = f(5, n − 1) + g(5, n − 1) + h(5, n − 1) We must use the two edges at each corner in any Hamiltonian path. We have three choices for the first edge of the path: up, down, or right. If the first edge is up, we get g(5, n − 1) ways to fill out the path, if down then f(5, n − 1) ways, and if right, then h(5, n − 1) ways.

We follow the same technique as in the previous two theorems. Let

F (5, x) = ∑_{n=1}^{∞} f(5, n)x^{n} F_{4}(5, x) = ∑_{n=1}^{∞} f_{4}(5, n)x^{n}
G(5, x) = ∑_{n=1}^{∞} g(5, n)x^{n} G_{4}(5, x) = ∑_{n=1}^{∞} g_{4}(5, n)x^{n}
F_{2}(5, x) = ∑_{n=1}^{∞} f_{2}(5, n)x^{n} F_{14,\overline{4}}(5, x) = ∑_{n=1}^{∞} f_{14,\overline{4}}(5, n)x^{n}
G_{2}(5, x) = ∑_{n=1}^{∞} g_{2}(5, n)x^{n} G_{14,\overline{4}}(5, x) = ∑_{n=1}^{∞} g_{14,\overline{4}}(5, n)x^{n}

H(5, x) = ∑_{n=1}^{∞} h(5, n)x^{n}

Then

F (5, x) = F_{2}(5, x) + x^{2}F_{4}(5, x) + x^{2}F (5, x)
G(5, x) = G_{2}(5, x) + x^{2}G_{4}(5, x) + x^{2}G(5, x)
F_{2}(5, x) = F_{14,\overline{4}}(5, x) + xF_{2}(5, x) + xG(5, x) + xH(5, x) + x^{2}F_{4}(5, x) + x
G_{2}(5, x) = G_{14,\overline{4}}(5, x) + xG_{2}(5, x) + xF (5, x) + xH(5, x) + x^{2}G_{4}(5, x)
F_{4}(5, x) = F_{14,\overline{4}}(5, x) + xG(5, x) + x^{2}F (5, x) + 2x^{2}F_{4}(5, x) + x
G_{4}(5, x) = G_{14,\overline{4}}(5, x) + xF (5, x) + x^{2}G(5, x) + 2x^{2}G_{4}(5, x)
F_{14,\overline{4}}(5, x) = xF_{14,\overline{4}}(5, x) + x^{2}F (5, x) + x^{2}F_{2}(5, x) + x^{2}G_{2}(5, x) + x^{2}H(5, x)
G_{14,\overline{4}}(5, x) = xG_{14,\overline{4}}(5, x) + x^{2}G(5, x) + x^{2}G_{2}(5, x) + x^{2}F_{2}(5, x) + x^{2}H(5, x)
H(5, x) = xF (5, x) + xG(5, x) + xH(5, x)

We rewrite this as a matrix equation.

[ \begin{matrix}x^{2} − 1 & 0 & 1 & 0 & x^{2} & 0 & 0 & 0 & 0 \\ 0 & x^{2} − 1 & 0 & 1 & 0 & x^{2} & 0 & 0 & 0 \\ 0 & x & x − 1 & 0 & x^{2} & 0 & 1 & 0 & x \\ x & 0 & 0 & x − 1 & 0 & x^{2} & 0 & 1 & x \\ x^{2} & x & 0 & 0 & 2x^{2} − 1 & 0 & 1 & 0 & 0 \\ x & x^{2} & 0 & 0 & 0 & 2x^{2} − 1 & 0 & 1 & 0 \\ x^{2} & 0 & x^{2} & x^{2} & 0 & 0 & x − 1 & 0 & x^{2} \\ 0 & x^{2} & x^{2} & x^{2} & 0 & 0 & 0 & x − 1 & x^{2} \\ x & x & 0 & 0 & 0 & 0 & 0 & 0 & x − 1 \end{matrix} ]·[ \begin{matrix}F (5, x) \\ G(5, x) \\ F_{2}(5, x) \\ G_{2}(5, x) \\ F_{4}(5, x) \\ G_{4}(5, x) \\ F_{14,\overline{4}}(5, x) \\ G_{14,\overline{4}}(5, x) \\ H(5, x) \end{matrix} ]

= [ 0 0 −x 0 −x 0 0 0 0 ]^{T}

We solve for the functions by finding the inverse of the matrix and multiplying it by the column vector [0, 0, −x, 0, −x, 0, 0, 0, 0]. The determinant of the matrix is p(x)(x − 1). To do this computation, we originally used Macsyma. The same computation can be done on Maple or Mathematica. Then H(5, x) has denominator x^{7} + 7x^{5} − 10x^{3} + 3x^{2} + 4x − 1. The other functions (except F (5, x) and G(5, x)) have denominator p(x)/(x + 1). □

4 Conjectures

Let F (m, x) = ∑_{n=1}^{∞} f(m, n)x^{n} and G(m, x) = ∑_{n=1}^{∞} g(m, n)x^{n}. The hard part of computing the rational polynomials that correspond to these functions for m = 3, 4, 5 is in choosing a small enough set of related functions which can each be described in terms of the others. It is easy to believe that some such set of functions always does exist.

Coven, Kitchens and Silberger [1] have shown, using the transfer matrix method (see [11]) that F (m, x) and G(m, x) are always rational polynomials.

Conjecture 1 F (m, x) and G(m, x) are rational polynomials with the same denominator.

The degrees of the denominators of F (k, x) and G(k, x) are 1, 8, and 12 for k = 3, 4, 5 respectively. In each case, the generating functions are in lowest terms as rational polynomials. Hence these functions cannot satisfy any recurrence of lower degree [11]. The degree of the denominator of the rational generating function for the number of Hamiltonian cycles in a grid are 4 and 6 for k = 4, 5 respectively, see [6, 7, 13]. Generally, the greater the degree, the longer the recurrence and the harder it is to find.

Most of the constraints used here to find recurrences relate to the outside border of the grid. As the grid gets bigger, these kind of constraints will have less effect on the total number of paths. The recurrences probably become longer and more complicated.

Conjecture 2 The degree of the denominator of F (m, x) and G(m, x) as m goes to ∞ is exponential in m.

Conjecture 3 ^{1} Let v and u be two vertices on the outside perimeter of an m × n grid. If a Hamiltonian path exists from v to u, add an edge between u and v to make a Hamiltonian cycle in the resulting graph. Then the number of squares inside this cycle is the same for any Hamiltonian path in the grid between u and v. Additionally, if the smaller of the two distances from v to u along the outside boundary cycle of the grid is d, then the minimum of the number of squares inside the Hamiltonian cycle and the number of squares outside the Hamiltonian cycle is (mn − 2m − 2n + d + 3)/2.

1This conjecture has been proved by D. Fisher using Pick’s Theorem

The authors would like to thank Ellen Gethner for suggesting the problem and Y. H. Harris Kwong and the referees for helpful comments.

References

[1] E. Coven, B. Kitchens, S. Silberger, personal communication.

[2] H. Everett (1986) Finding Hamiltonian paths in nonrectangular grid graphs, Congr. Numer. 53 185-192.

[3] F. Göbel (1979) Hamilton cycles in product graphs, Technische Hogeschool Twente, Memorandum Nr. 268.

[4] F. Göbel (1979) On the number of Hamilton cycles in product graphs, Technische Hogeschool Twente, Memorandum Nr. 289.

[5] A. Itai, C. H. Papadimitriou and J. L. Szwarcfiter (1982) Hamilton paths in grid graphs, SIAM J. Comput. 11 676-686.

[6] G. Kreweras (1992) Dénombrement des Cycles Hamiltoniens dans un Rectangle Quadrillé, Europ. J. Comb. 13 473-476.

[7] Y. H. H. Kwong (1992) Enumeration of Hamiltonian cycles in P_{4} × P_{n} and P_{5} × P_{n}, Ars Comb. 33 87-96.

[8] F. Luccio and C. Mugnai (1978) Hamiltonian paths on a rectangular chessboard, 16th Annual Allerton Conference, 73-78.

[9] H. Niederhausen (1982) How many paths cross at least l given lattice points?, Congr. Numer. 36 161-173.

[10] B. R. Myers (1981) Enumeration of tours in Hamiltonian rectangular lattice graphs, Math Magazine 54 19-23.

[11] R. P. Stanley (1986) Enumerative Combinatorics Volume I, Wadsworth and Brooks Cole, Monterey CA.

[12] R. Stoyan (1993) Anzahl der Hamilton-Kreise in Rechteckigen Gettern, Thesis, University of Erlangen-Nuernberg, Erlangen, Germany.

[13] R. Tos̆ić, O. Bodrŏza, Y. H. H. Kwong, and H. J. Straight (1990) On the number of Hamiltonian cycles of P_{4} × P_{n}, Indian J. of Pure and Appl Math 21 403-409.

[14] C. Zamfirescu and T. Zamfirescu (1992) Hamiltonian properties of grid graphs, SIAM J. of Discr. Math. 5 564-570.