Not every 2-tough graph is hamiltonian

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

Research output: Contribution to journalArticleAcademicpeer-review

43 Citations (Scopus)
41 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

    Fingerprint

Keywords

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

Cite this