標題: 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-Mar-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
Appears in Collections:Articles


Files in This Item:

  1. 000180427500005.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.