# Hamiltonian properties of almost locally connected claw-free graphs

Xiaodong Chen, MingChu Li, Wei Liao, Haitze J. Broersma

### Abstract

A vertex v of a graph G is locally connected if the set of neighbors N(v) of v induces a connected subgraph in G. Let B(G) denote the set of vertices of G that are not locally connected. Then G is almost locally connected if B(G) is an independent set and for any vertex x in B(G), there is a vertex y in V(G) - x such that N(x) ∪ y induces a connected subgraph of G. The main result of this paper is that an almost locally connected claw-free graph on at least 4 vertices is Hamilton-connected if and only if it is 3-connected. This generalizes the result by Asratian that a locally connected claw-free graph on at least 4 vertices is Hamilton-connected if and only if it is 3-connected [Journal of Graph Theory 23 (1996) 191–201].
Original language Undefined 95-109 15 Ars combinatoria 124 Published - Jan 2016

### Keywords

• EWI-27151
• MSC-05C
• IR-101070
• METIS-318496
• Hamilton-connected
• Hamiltonian
• almost locally connected
• Claw-free graph

### Cite this

Chen, Xiaodong ; Li, MingChu ; Liao, Wei ; Broersma, Haitze J. / Hamiltonian properties of almost locally connected claw-free graphs. In: Ars combinatoria. 2016 ; Vol. 124. pp. 95-109.
@article{14f0afc5ed0943a0a247e5efa94d3b81,
title = "Hamiltonian properties of almost locally connected claw-free graphs",
abstract = "A vertex v of a graph G is locally connected if the set of neighbors N(v) of v induces a connected subgraph in G. Let B(G) denote the set of vertices of G that are not locally connected. Then G is almost locally connected if B(G) is an independent set and for any vertex x in B(G), there is a vertex y in V(G) - x such that N(x) ∪ y induces a connected subgraph of G. The main result of this paper is that an almost locally connected claw-free graph on at least 4 vertices is Hamilton-connected if and only if it is 3-connected. This generalizes the result by Asratian that a locally connected claw-free graph on at least 4 vertices is Hamilton-connected if and only if it is 3-connected [Journal of Graph Theory 23 (1996) 191–201].",
keywords = "EWI-27151, MSC-05C, IR-101070, METIS-318496, Hamilton-connected, Hamiltonian, almost locally connected, Claw-free graph",
author = "Xiaodong Chen and MingChu Li and Wei Liao and Broersma, {Haitze J.}",
note = "eemcs-eprint-27151",
year = "2016",
month = "1",
language = "Undefined",
volume = "124",
pages = "95--109",
journal = "Ars combinatoria",
issn = "0381-7032",
publisher = "Charles Babbage Research Centre",

}

Hamiltonian properties of almost locally connected claw-free graphs. / Chen, Xiaodong; Li, MingChu; Liao, Wei; Broersma, Haitze J.

In: Ars combinatoria, Vol. 124, 01.2016, p. 95-109.

TY - JOUR

T1 - Hamiltonian properties of almost locally connected claw-free graphs

AU - Chen, Xiaodong

AU - Li, MingChu

AU - Liao, Wei

AU - Broersma, Haitze J.

N1 - eemcs-eprint-27151

PY - 2016/1

Y1 - 2016/1

N2 - A vertex v of a graph G is locally connected if the set of neighbors N(v) of v induces a connected subgraph in G. Let B(G) denote the set of vertices of G that are not locally connected. Then G is almost locally connected if B(G) is an independent set and for any vertex x in B(G), there is a vertex y in V(G) - x such that N(x) ∪ y induces a connected subgraph of G. The main result of this paper is that an almost locally connected claw-free graph on at least 4 vertices is Hamilton-connected if and only if it is 3-connected. This generalizes the result by Asratian that a locally connected claw-free graph on at least 4 vertices is Hamilton-connected if and only if it is 3-connected [Journal of Graph Theory 23 (1996) 191–201].

AB - A vertex v of a graph G is locally connected if the set of neighbors N(v) of v induces a connected subgraph in G. Let B(G) denote the set of vertices of G that are not locally connected. Then G is almost locally connected if B(G) is an independent set and for any vertex x in B(G), there is a vertex y in V(G) - x such that N(x) ∪ y induces a connected subgraph of G. The main result of this paper is that an almost locally connected claw-free graph on at least 4 vertices is Hamilton-connected if and only if it is 3-connected. This generalizes the result by Asratian that a locally connected claw-free graph on at least 4 vertices is Hamilton-connected if and only if it is 3-connected [Journal of Graph Theory 23 (1996) 191–201].

KW - EWI-27151

KW - MSC-05C

KW - IR-101070

KW - METIS-318496

KW - Hamilton-connected

KW - Hamiltonian

KW - almost locally connected

KW - Claw-free graph

M3 - Article

VL - 124

SP - 95

EP - 109

JO - Ars combinatoria

JF - Ars combinatoria

SN - 0381-7032

ER -