TY - JOUR

T1 - Proper interval graphs and the guard problem 1

AU - Chen, Chiuyuan

AU - Chang, Chin Chen

AU - Chang, Gerard J.

PY - 1997/6/10

Y1 - 1997/6/10

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

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

KW - Guard

KW - Hamiltonian path (cycle)

KW - Hamiltonian-connected

KW - Proper interval graph

KW - Spiral polygon

KW - Visibility

UR - http://www.scopus.com/inward/record.url?scp=0041629045&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(96)00307-X

DO - 10.1016/S0012-365X(96)00307-X

M3 - Article

AN - SCOPUS:0041629045

VL - 170

SP - 223

EP - 230

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

ER -