Proper interval graphs and the guard problem

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 greater than or equal to 2 vertices have hamiltonian paths, those with greater than or equal to 3 vertices have hamiltonian cycles, and those with greater than or equal to 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.