Hamilton cycles in sparse locally connected graphs

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

doi:10.1016/j.dam.2018.10.031

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

Department of Applied Mathematics and Computer Science

Research output: Contribution to journal › Journal article › Research › peer-review

144 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 + klog₂n, but NP-complete if m = 2n + [n^1/k].

Original language	English
Journal	Discrete Applied Mathematics
Volume	257
Number of pages	13
ISSN	0166-218X
DOIs	https://doi.org/10.1016/j.dam.2018.10.031
Publication status	Published - 2019

Keywords

Locally connected
NP-complete
Polynomial time algorithm
Hamiltonians

Access to Document

10.1016/j.dam.2018.10.031

FulltextAccepted author manuscript, 718 KB

OpenUrl availability

Full text

Cite this

@article{fed9afbe525d4653b6804ab348374bc4,

title = "Hamilton cycles in sparse locally connected graphs",

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].",

keywords = "Locally connected, NP-complete, Polynomial time algorithm, Hamiltonians",

author = "{van Aardt}, {Susan A.} and Burger, {Alewyn P.} and Marietjie Frick and Carsten Thomassen and {de Wet}, {Johan P.}",

year = "2019",

doi = "10.1016/j.dam.2018.10.031",

language = "English",

volume = "257",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

}

TY - JOUR

T1 - Hamilton cycles in sparse locally connected graphs

AU - van Aardt, Susan A.

AU - Burger, Alewyn P.

AU - Frick, Marietjie

AU - Thomassen, Carsten

AU - de Wet, Johan P.

PY - 2019

Y1 - 2019

N2 - 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].

AB - 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].

KW - Locally connected

KW - NP-complete

KW - Polynomial time algorithm

KW - Hamiltonians

U2 - 10.1016/j.dam.2018.10.031

DO - 10.1016/j.dam.2018.10.031

M3 - Journal article

SN - 0166-218X

VL - 257

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Hamilton cycles in sparse locally connected graphs

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this