06-15
Hamiltonian Properties of Triangular Grid Graphs
by Gordon, V.S.; Orlovich, Y.L.; Werner, F.
Preprint series: 06-15, Preprints
The paper is published: Discrete Mathematics, Vol. 308, No. 24, 2008, 6166 - 6188.
- MSC:
- 05C38 Paths and cycles, See also {90B10}
- 05C45 Eulerian and Hamiltonian graphs
- 68Q25 Analysis of algorithms and problem complexity
Abstract: A triangular grid gaph 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.
Keywords: Hamiltonian graph, Triangular grid graph, Local connectivity, NP-completeness
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.