Hamiltonian cycles in triangular grids

Valentin Polishchuk; Esther M. Arkin; Joseph S.B. Mitchell

Hamiltonian cycles in triangular grids

Valentin Polishchuk
, Esther M. Arkin
, Joseph S.B. Mitchell

Applied Mathematics and Statistics

Stony Brook University

Stony Brook University

Research output: Contribution to conference › Paper › peer-review

7 Scopus citations

Abstract

We study the Hamiltonian Cycle problem in graphs induced by subsets of the vertices of the tiling of the plane with equilateral triangles. By analogy with grid graphs we call such graphs triangular grid graphs. Following the analogy, we define the class of solid triangular grid graphs. We prove that the Hamiltonian Cycle problem is NP-complete for triangular grid graphs. We show that with the exception of the “Star of David”, a solid triangular grid graph without cut vertices is always Hamiltonian.

Original language	English
Pages	63-66
Number of pages	4
State	Published - 2006
Event	18th Annual Canadian Conference on Computational Geometry, CCCG 2006 - Kingston, Canada Duration: Aug 14 2006 → Aug 16 2006

Conference

Conference	18th Annual Canadian Conference on Computational Geometry, CCCG 2006
Country/Territory	Canada
City	Kingston
Period	08/14/06 → 08/16/06

Cite this

@conference{99807646b33c4ec29918d79c5fc54b37,

title = "Hamiltonian cycles in triangular grids",

abstract = "We study the Hamiltonian Cycle problem in graphs induced by subsets of the vertices of the tiling of the plane with equilateral triangles. By analogy with grid graphs we call such graphs triangular grid graphs. Following the analogy, we define the class of solid triangular grid graphs. We prove that the Hamiltonian Cycle problem is NP-complete for triangular grid graphs. We show that with the exception of the “Star of David”, a solid triangular grid graph without cut vertices is always Hamiltonian.",

author = "Valentin Polishchuk and Arkin, \{Esther M.\} and Mitchell, \{Joseph S.B.\}",

note = "Publisher Copyright: {\textcopyright} 2006 Canadian Conference on Computational Geometry. All rights reserved.; 18th Annual Canadian Conference on Computational Geometry, CCCG 2006 ; Conference date: 14-08-2006 Through 16-08-2006",

year = "2006",

language = "English",

pages = "63--66",

}

TY - CONF

T1 - Hamiltonian cycles in triangular grids

AU - Polishchuk, Valentin

AU - Arkin, Esther M.

AU - Mitchell, Joseph S.B.

PY - 2006

Y1 - 2006

N2 - We study the Hamiltonian Cycle problem in graphs induced by subsets of the vertices of the tiling of the plane with equilateral triangles. By analogy with grid graphs we call such graphs triangular grid graphs. Following the analogy, we define the class of solid triangular grid graphs. We prove that the Hamiltonian Cycle problem is NP-complete for triangular grid graphs. We show that with the exception of the “Star of David”, a solid triangular grid graph without cut vertices is always Hamiltonian.

AB - We study the Hamiltonian Cycle problem in graphs induced by subsets of the vertices of the tiling of the plane with equilateral triangles. By analogy with grid graphs we call such graphs triangular grid graphs. Following the analogy, we define the class of solid triangular grid graphs. We prove that the Hamiltonian Cycle problem is NP-complete for triangular grid graphs. We show that with the exception of the “Star of David”, a solid triangular grid graph without cut vertices is always Hamiltonian.

UR - https://www.scopus.com/pages/publications/84867987182

M3 - Paper

SP - 63

EP - 66

T2 - 18th Annual Canadian Conference on Computational Geometry, CCCG 2006

Y2 - 14 August 2006 through 16 August 2006

ER -

Hamiltonian cycles in triangular grids

Abstract

Conference

Other files and links

Fingerprint

Cite this