Enumeration of Hamiltonian cycles in some grid graphs

Abstract

In polymer science, Hamiltonian paths and Hamiltonian circuits can serve as excellent simple models for dense packed globular proteins. Generation and enumeration of Hamiltonian paths and Hamiltonian circuits (compact conformations of a chain) are needed to investigate thermodynamics of protein folding. Hamiltonian circuits are a mathematical idealization of polymer melts, too. The number of Hamiltonian cycles on a graph corresponds to the entropy of a polymer system. In this paper, we present new characterizations of the Hamiltonian cycles in a labeled rectangular grid graph Pm ×Pn and in a labeled thin cylinder grid graph Cm×Pn. We proved that for any fixed m, the numbers of Hamiltonian cycles in these grid graphs, as sequences with counter n, are determined by linear recurrences. The computational method outlined here for finding these difference equations together with the initial terms of the sequences has been implemented. The generating functions of the sequences are given explicitly for some values of m. The obtained data are consistent with data obtained in the works by Kloczkowski and Jernigan, and Schmalz et al.