Proper interval graphs and the guard problem 1

Chiuyuan Chen*, Chin Chen Chang, Gerard J. Chang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

This paper is a study of the hamiltonicity of proper interval graphs with applications to the guard problem in spiral polygons. We prove that proper interval graphs with ≥2 vertices have hamiltonian paths, those with ≥3 vertices have hamiltonian cycles, and those with ≥4 vertices are hamiltonian-connected if and only if they are, respectively, 1-, 2-, or 3-connected. We also study the guard problem in spiral polygons by connecting the class of nontrivial connected proper interval graphs with the class of stick-intersection graphs of spiral polygons.

Original languageEnglish
Pages (from-to)223-230
Number of pages8
JournalDiscrete Mathematics
Volume170
Issue number1-3
DOIs
StatePublished - 10 Jun 1997

Keywords

  • Guard
  • Hamiltonian path (cycle)
  • Hamiltonian-connected
  • Proper interval graph
  • Spiral polygon
  • Visibility

Fingerprint Dive into the research topics of 'Proper interval graphs and the guard problem 1'. Together they form a unique fingerprint.

Cite this