Two New Classes of Hamiltonian Graphs. (Extended Abstract)

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

doi:10.1016/j.endm.2007.07.090

Two New Classes of Hamiltonian Graphs. (Extended Abstract)

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

Applied Mathematics and Statistics

University of Helsinki

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

We prove that a triangular grid without local cuts is (almost) always Hamiltonian. This suggests an efficient scheme for rendering triangulated manifolds by graphics hardware. We also show that the Hamiltonian Cycle problem is NP-Complete for planar subcubic graphs of arbitrarily high girth. As a by-product we prove that there exist tri-Hamiltonian planar subcubic graphs of arbitrarily high girth.

Original language	English
Pages (from-to)	565-569
Number of pages	5
Journal	Electronic Notes in Discrete Mathematics
Volume	29
Issue number	SPEC. ISS.
DOIs	https://doi.org/10.1016/j.endm.2007.07.090
State	Published - Aug 15 2007

Keywords

Girth
Grid graph
Hamiltonian cycle

Access to Document

10.1016/j.endm.2007.07.090

Cite this

@article{081c7a2fd2664fccab747e7c1445ff47,

title = "Two New Classes of Hamiltonian Graphs. (Extended Abstract)",

abstract = "We prove that a triangular grid without local cuts is (almost) always Hamiltonian. This suggests an efficient scheme for rendering triangulated manifolds by graphics hardware. We also show that the Hamiltonian Cycle problem is NP-Complete for planar subcubic graphs of arbitrarily high girth. As a by-product we prove that there exist tri-Hamiltonian planar subcubic graphs of arbitrarily high girth.",

keywords = "Girth, Grid graph, Hamiltonian cycle",

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

year = "2007",

month = aug,

day = "15",

doi = "10.1016/j.endm.2007.07.090",

language = "English",

volume = "29",

pages = "565--569",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

number = "SPEC. ISS.",

}

TY - JOUR

T1 - Two New Classes of Hamiltonian Graphs. (Extended Abstract)

AU - Arkin, Esther M.

AU - Mitchell, Joseph S.B.

AU - Polishchuk, Valentin

PY - 2007/8/15

Y1 - 2007/8/15

N2 - We prove that a triangular grid without local cuts is (almost) always Hamiltonian. This suggests an efficient scheme for rendering triangulated manifolds by graphics hardware. We also show that the Hamiltonian Cycle problem is NP-Complete for planar subcubic graphs of arbitrarily high girth. As a by-product we prove that there exist tri-Hamiltonian planar subcubic graphs of arbitrarily high girth.

AB - We prove that a triangular grid without local cuts is (almost) always Hamiltonian. This suggests an efficient scheme for rendering triangulated manifolds by graphics hardware. We also show that the Hamiltonian Cycle problem is NP-Complete for planar subcubic graphs of arbitrarily high girth. As a by-product we prove that there exist tri-Hamiltonian planar subcubic graphs of arbitrarily high girth.

KW - Girth

KW - Grid graph

KW - Hamiltonian cycle

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

U2 - 10.1016/j.endm.2007.07.090

DO - 10.1016/j.endm.2007.07.090

M3 - Article

AN - SCOPUS:34547667087

SN - 1571-0653

VL - 29

SP - 565

EP - 569

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

IS - SPEC. ISS.

ER -

Two New Classes of Hamiltonian Graphs. (Extended Abstract)

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this