Proper interval graphs and the guard problem
| dc.citation.epage | 230 | en_US |
| dc.citation.issue | 1-3 | en_US |
| dc.citation.spage | 223 | en_US |
| dc.citation.volume | 170 | en_US |
| dc.citation.woscount | 8 | |
| dc.contributor.author | Chen, CY | en_US |
| dc.contributor.author | Chang, CC | en_US |
| dc.contributor.author | Chang, GJ | en_US |
| dc.contributor.department | 應用數學系 | zh_TW |
| dc.contributor.department | Department of Applied Mathematics | en_US |
| dc.date.accessioned | 2014-12-08T15:01:42Z | |
| dc.date.available | 2014-12-08T15:01:42Z | |
| dc.date.issued | 1997-06-10 | en_US |
| dc.description.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. | en_US |
| dc.identifier.issn | 0012-365X | en_US |
| dc.identifier.journal | DISCRETE MATHEMATICS | en_US |
| dc.identifier.uri | https://ir.lib.nycu.edu.tw/handle/11536/490 | |
| dc.identifier.wosnumber | WOS:A1997XF48000017 | |
| dc.language.iso | en_US | en_US |
| dc.subject | proper interval graph | en_US |
| dc.subject | Hamiltonian path (cycle) | en_US |
| dc.subject | Hamiltonian-connected | en_US |
| dc.subject | guard | en_US |
| dc.subject | visibility | en_US |
| dc.subject | spiral polygon | en_US |
| dc.title | Proper interval graphs and the guard problem | en_US |
| dc.type | Article | en_US |