標題: | Any maximal planar graph with only one separating triangle is hamiltonian |
作者: | Chen, CY 應用數學系 Department of Applied Mathematics |
關鍵字: | planar graph;maximal planar graph;hamiltonian cycle;separating triangle;NP-complete |
公開日期: | 1-三月-2003 |
摘要: | A graph is hamiltonian if it has a hamiltonian cycle. It is well-known that Tutte proved that any 4-connected planar graph is hamiltonian. It is also well-known that the problem of determining whether a 3-connected planar graph is hamiltonian is NP-complete. In particular, Chvatal and Wigderson had independently shown that the problem of determining whether a maximal planar graph is hamiltonian is NP-complete. A classical theorem of Whitney says that any maximal planar graph with no separating triangles is hamiltonian, where a separating triangle is a triangle whose removal separates the graph. Note that if a planar graph has separating triangles, then it can not be 4-connected and therefore Tutte's result can not be applied. In this paper, we shall prove that any maximal planar graph with only one separating triangle is still hamiltonian. |
URI: | http://dx.doi.org/10.1023/A:1021998507140 http://hdl.handle.net/11536/28040 |
ISSN: | 1382-6905 |
DOI: | 10.1023/A:1021998507140 |
期刊: | JOURNAL OF COMBINATORIAL OPTIMIZATION |
Volume: | 7 |
Issue: | 1 |
起始頁: | 79 |
結束頁: | 86 |
顯示於類別: | 期刊論文 |