CYCLIC PROPERTIES OF TRIANGULAR GRID GRAPHS

It is known that all 2-connected, linearly convex triangular grid graphs, with only one exception, are hamiltonian (Reay and Zamfirescu, 2000). In the paper, it is shown that this result holds for a wider class of connected, locally connected triangular grid graphs and, with more exceptions, even for some general class of graphs. It is also shown that the HAMILTONIAN CYCLE problem is NP-complete for triangular grid graphs.