Let G be a graph on n ≥ 3 vertices. A graph G is almost distance-hereditary if each connected induced subgraph H of G has the property dH(x, y) ≤ dG(x, y) + 1 for any pair of vertices x, y ∈ V(H). Adopting the terminology introduced by Broersma et al. and Čada, a graph G is called 1-heavy if at least one of the end vertices of each induced subgraph of G isomorphic to K1,3 (a claw) has degree at least n/2, and is called claw-heavy if each claw of G has a pair of end vertices with degree sum at least n. In this paper we prove the following two theorems: (1) Every 2-connected, claw-heavy and almost distance-hereditary graph is Hamiltonian. (2) Every 3-connected, 1-heavy and almost distance-hereditary graph is Hamiltonian. The first result improves a previous theorem of Feng and Guo [J.-F. Feng and Y.-B. Guo, Hamiltonian cycle in almost distance-hereditary graphs with degree condition restricted to claws, Optimazation 57 (2008), no. 1, 135–141]. For the second result, its connectedness condition is sharp since Feng and Guo constructed a 2-connected 1-heavy graph which is almost distance-hereditary but not Hamiltonian.
@article{bwmeta1.element.doi-10_1515_math-2016-0003,
author = {Bing Chen and Bo Ning},
title = {Hamilton cycles in almost distance-hereditary graphs},
journal = {Open Mathematics},
volume = {14},
year = {2016},
pages = {19-28},
zbl = {1346.05134},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_1515_math-2016-0003}
}
Bing Chen; Bo Ning. Hamilton cycles in almost distance-hereditary graphs. Open Mathematics, Tome 14 (2016) pp. 19-28. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_1515_math-2016-0003/