# Hamilton cycles in almost distance-hereditary graphs

Open Mathematics (2016)

- Volume: 14, Issue: 1, page 19-28
- ISSN: 2391-5455

## Access Full Article

top## Abstract

top## How to cite

topBing 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 -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.