|
|||||
|
|
Hamiltonian properties of triangular grid graphs |
|
| Authors: | Valery S Gordon Frank Werner |
| Institution: | a United Institute of Informatics Problems, National Academy of Sciences of Belarus, 6 Surganova Str., 220012 Minsk, Belarus b Department of Combinatorial Models and Algorithms, Institute of Mathematics, National Academy of Sciences of Belarus, 11 Surganova Str., 220072 Minsk, Belarus c Institute of Mathematical Optimization, Otto-von-Guericke-University of Magdeburg, Universitätsplatz 2, 39106 Magdeburg, Germany |
| Abstract: | A triangular grid graph is a finite induced subgraph of the infinite graph associated with the two-dimensional triangular grid. In 2000, 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 D 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 of graph D) 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. |
| Keywords: | Hamiltonian graph Triangular grid graph Local connectivity NP-completeness |
| 本文献已被 ScienceDirect 等数据库收录！ | |