Hamilton cycles in almost distance-hereditary graphs

Bing Chen, and Bo Ning. "Hamilton cycles in almost distance-hereditary graphs." Open Mathematics 14.1 (2016): 19-28. <http://eudml.org/doc/276864>.

@article{BingChen2016,
abstract = {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.},
author = {Bing Chen, Bo Ning},
journal = {Open Mathematics},
keywords = {Hamilton cycle; Almost distance-hereditary graph; Claw-free graph; 1-heavy graph; 2-heavy graph; Claw-heavy graph; almost distance-hereditary graph; claw-free graph; claw-heavy graph},
language = {eng},
number = {1},
pages = {19-28},
title = {Hamilton cycles in almost distance-hereditary graphs},
url = {http://eudml.org/doc/276864},
volume = {14},
year = {2016},
}

TY - JOUR
AU - Bing Chen
AU - Bo Ning
TI - Hamilton cycles in almost distance-hereditary graphs
JO - Open Mathematics
PY - 2016
VL - 14
IS - 1
SP - 19
EP - 28
AB - 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.
LA - eng
KW - Hamilton cycle; Almost distance-hereditary graph; Claw-free graph; 1-heavy graph; 2-heavy graph; Claw-heavy graph; almost distance-hereditary graph; claw-free graph; claw-heavy graph
UR - http://eudml.org/doc/276864
ER -