Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 79-86 |
Number of pages | 8 |
Journal | Journal of Combinatorial Optimization |
Volume | 7 |
Issue number | 1 |
DOIs | |
State | Published - 1 Mar 2003 |
Keywords
- Hamiltonian cycle
- Maximal planar graph
- NP-complete
- Planar graph
- Separating triangle