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

40 Downloads (Pure)

Abstract

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
Volume257
Number of pages13
ISSN0166-218X
DOIs
Publication statusPublished - 2019

Keywords

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

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

Cite this