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 languageUndefined
Pages (from-to)95-109
Number of pages15
JournalArs combinatoria
Volume124
StatePublished - Jan 2016

Fingerprint

Locally connected
Claw-free graphs
Connected graph
Subgraph
Vertex of a graph
If and only if
Independent set
Graph theory
Denote
Generalise
Graph in graph theory

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, Vol. 124, 01.2016, p. 95-109.

Research output: Scientific - peer-reviewArticle

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

Research output: Scientific - peer-reviewArticle

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

T2 - Ars combinatoria

JF - Ars combinatoria

SN - 0381-7032

ER -