Not every 2-tough graph is hamiltonian

Haitze J. Broersma, D. Bauer, H.J. Veldman

Research output: Contribution to journalArticleAcademicpeer-review

47 Citations (Scopus)
60 Downloads (Pure)

Abstract

We present (9/4-ε)-tough graphs without a Hamilton path for arbitrary >0, thereby refuting a well-known conjecture due to Chvátal. We also present (7/4-ε) -tough chordal graphs without a Hamilton path for any ε>0.
Original languageEnglish
Pages (from-to)317-321
Number of pages5
JournalDiscrete applied mathematics
Volume2000
Issue number99
DOIs
Publication statusPublished - 2000

Keywords

  • Toughness
  • Traceable graph
  • Chordal graph
  • Hamiltonian graph
  • 2-tough graph

Fingerprint Dive into the research topics of 'Not every 2-tough graph is hamiltonian'. Together they form a unique fingerprint.

  • Cite this