Some new characterizations of Hamiltonian cycles in triangular grid graphs

In the studies that have been devoted to the protein folding problem, which is one of the great unsolved problems of science, some specific graphs, like the so-called triangular grid graphs, have been used as a simplified lattice model. Generation and enumeration of Hamiltonian paths and Hamiltonian circuits (compact conformations of a chain) are needed to investigate the thermodynamics of protein folding. In this paper, we present new characterizations of the Hamiltonian cycles in labeled triangular grid graphs, which are graphs constructed from rectangular grids by adding a diagonal to each cell. By using these characterizations and implementing the computational method outlined here, we confirm the existing data, and obtain some new results that have not been published. A new interpretation of Catalan numbers is also included.