Finding Hamiltonian Cycles in Four Subfamilies of Quasi-Claw-Free Graphs

Abstract

A graph \(G\) is called quasi-claw-free if it satisfies the property:\(d(x,y) = 2 \Rightarrow \text{there exists} u \in N(x) \cap N(y) \text{ such that } N[u] \subseteq N[x] \cup N[y].\) It is shown that a Hamiltonian cycle can be found in polynomial time in four subfamilies of quasi-claw-free graphs.