Hamiltonian properties of triangular grid graphs

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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2008-12, Vol.308 (24), p.6166-6188
Main Authors: Gordon, Valery S., Orlovich, Yury L., Werner, Frank
Format: Article
Language:English
Subjects:
Applied sciences
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
Graph theory
Hamiltonian graph
Information retrieval. Graph
Local connectivity
Mathematics
NP-completeness
Sciences and techniques of general use
Theoretical computing
Triangular grid graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2007.11.040