Séminaire Lotharingien de Combinatoire, B34f (1995), 21pp.

Robert Stoyan and Volker Strehl

Enumeration of Hamiltonian Circuits in Rectangular Grids

Abstract. We describe an algorithm for computing the number h(m,n) of Hamiltonian circuits in a m-by-n rectangular grid graph. For any fixed m, the set of Hamiltonian circuits on such graphs (for varying n) can be identified via an appropriate coding with the words of a certain regular language L(m). We show how to systematically construct a finite automaton A(m) recognizing L(m). This allows, in principle, the computation of the (rational) generating function h(m)(z) of L(m). We exhibit a bijection between the states of A(m) and the words of length m+1 of the familiar Motzkin language. This yields an upper bound on the degree of the denominator polynomial of h(m)(z), hence of the order of the linear recurrence satisfied by the coefficients h(m,n) for fixed m.

The method described here has been implemented. Numerical data resulting from this implementation are presented at the end of this article.

The following versions are available: