Hamiltonian Properties of Almost Locally Connected Claw-Free Graphs

Xiaodong Chen1, MingChu Li2, Wei Liao2, Hajo Broersma3
1College of Science, Liaoning University of Technology, Jinzhou 121001, P.R. China
2School of Software, Dalian University of Technology, Dalian, 116024, P.R. China
3 Faculty of EEMCS, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands

Abstract

is almost locally connected if \(B(G)\) is an independent set and for any \(x \in B(G)\), there is a vertex \(y\) in \(V(G) \setminus \{x\}\) such that \(N(x) \cup \{y\}\) induces a connected subgraph of \(G\), where \(B(G)\) denotes the set of vertices of \(G\) that are not locally connected. In this paper, we prove 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 a 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\)].