Hamiltonian cycle in almost distance-hereditary graphs with degree condition restricted to claws†

†Dedicated to Prof. Dr Dr h.c. Hubertus Th. Jongen on his 60th birthday.

Abstract

Let G = (V(G), E(G)) be a connected graph. The distance between two vertices x and y in G, denoted by d_G (x, y), is the length of a shortest path between x and y. A graph G is called almost distance-hereditary, if each connected induced subgraph H of G has the property that d_H (u, v) ≤ d_G (u, v) + 1 for every pair of vertices u and v in H. A graph G is 2-heavy if the degree of at least two end vertices of each claw in G are greater than or equal to |V(G)|/2. We show that every 2-connected, 2-heavy and almost distance-hereditary graph has a Hamiltonian cycle. This generalizes the main result of [8] that states: every 2-connected, claw-free and almost distance-hereditary graph is Hamiltonian.

†Dedicated to Prof. Dr Dr h.c. Hubertus Th. Jongen on his 60th birthday.

Keywords:

• claw
• degree condition
• induced subgraph
• distance-hereditary
• Hamiltonian cycle

Mathematics Subject Classifications 2000: :

• 05C38
• 05C45

Notes

†Dedicated to Prof. Dr Dr h.c. Hubertus Th. Jongen on his 60th birthday.