Enumeration of Hamiltonian Circuits in Rectangular Grids
Séminaire lotharingien de combinatoire, Tome 34 (1995)
Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website
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.
@article{SLC_1995_34_a5,
author = {Robert Stoyan and Volker Strehl},
title = {Enumeration of {Hamiltonian} {Circuits} in {Rectangular} {Grids}},
journal = {S\'eminaire lotharingien de combinatoire},
publisher = {mathdoc},
volume = {34},
year = {1995},
url = {http://geodesic.mathdoc.fr/item/SLC_1995_34_a5/}
}
Robert Stoyan; Volker Strehl. Enumeration of Hamiltonian Circuits in Rectangular Grids. Séminaire lotharingien de combinatoire, Tome 34 (1995). http://geodesic.mathdoc.fr/item/SLC_1995_34_a5/