Hamilton cycles in sparse locally connected graphs

Susan A. van Aardt, Alewyn P. Burger, Marietjie Frick, Carsten Thomassen, Johan P. de Wet*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

124 Downloads (Pure)


A graph G is locally connected if for every υ ε (G) the open neighbourhood N(υ) of υ is nonempty and induces a connected graph in G. We characterize locally connected graphs of order n with less than 2n edges and show that for any natural number k the Hamilton Cycle Problem for locally connected graphs of order n with m edges is polynomially solvable if m ≤ 2n + klog2n, but NP-complete if m = 2n + [n1/k].
Original languageEnglish
JournalDiscrete Applied Mathematics
Number of pages13
Publication statusPublished - 2019


  • Locally connected
  • NP-complete
  • Polynomial time algorithm
  • Hamiltonians


Dive into the research topics of 'Hamilton cycles in sparse locally connected graphs'. Together they form a unique fingerprint.

Cite this