Hamilton cycles in almost distance-hereditary graphs

• Autorzy: Bing Chen , Bo Ning
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Hamilton cycle; Almost distance-hereditary graph; Claw-free graph; 1-heavy graph; 2-heavy graph; Claw-heavy graph

Kategorie tematyczne

• 05C45: Eulerian and Hamiltonian graphs
• 05C38: Paths and cycles

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2016
• Tom: 14
• Numer: 1
• Strony: 19-28

Daty

wydano

2016-01-01

otrzymano

2015-08-04

zaakceptowano

2015-10-27

online

2016-02-09

Twórcy

autor

Bing Chen

• Department of Applied Mathematics, School of Science, Xi’an University of Technology, Xi’an, Shaanxi 710048, P.R.

autor

Bo Ning

• Center for Applied Mathematics, Tianjin University, Tianjin, 300072, P.R.

Identyfikatory

DOI

10.1515/math-2016-0003