Any maximal planar graph with only one separating triangle is Hamiltonian

Chiuyuan Chen*

*Corresponding author for this work

Research output: Contribution to journalArticle

11 Scopus citations

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 languageEnglish
Pages (from-to)79-86
Number of pages8
JournalJournal of Combinatorial Optimization
Volume7
Issue number1
DOIs
StatePublished - 1 Mar 2003

Keywords

  • Hamiltonian cycle
  • Maximal planar graph
  • NP-complete
  • Planar graph
  • Separating triangle

Fingerprint Dive into the research topics of 'Any maximal planar graph with only one separating triangle is Hamiltonian'. Together they form a unique fingerprint.

  • Cite this