Hamiltonian properties of triangular grid graphs

What is it about?

A triangular grid graph is a finite induced subgraph of the infinite graph associated with the two-dimensional triangular grid. Reay and Zamfirescu showed that all 2-connected, linearly-convex triangular grid graphs (with the exception of one of them) are hamiltonian. The only exception is a graph which is the linearly-convex hull of the Star of David. We extend this result to a wider class of locally connected triangular grid graphs. Namely, we prove that all connected, locally connected triangular grid graphs (with the same exception) are hamiltonian. Moreover, we present a sufficient condition for a connected graph to be fully cycle extendable. We also show that the problem Hamiltonian Cycle is NP-complete for triangular grid graphs.

Featured Image