標題: Proper interval graphs and the guard problem
作者: Chen, CY
Chang, CC
Chang, GJ
應用數學系
Department of Applied Mathematics
關鍵字: proper interval graph;Hamiltonian path (cycle);Hamiltonian-connected;guard;visibility;spiral polygon
公開日期: 10-六月-1997
摘要: 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.
URI: http://hdl.handle.net/11536/490
ISSN: 0012-365X
期刊: DISCRETE MATHEMATICS
Volume: 170
Issue: 1-3
起始頁: 223
結束頁: 230
顯示於類別:期刊論文


文件中的檔案:

  1. A1997XF48000017.pdf