Hamiltonicity of 3-connected quasi-claw-free graphs. (Q1874377): Difference between revisions

A graph \(G\) is called claw-free, if no neighborhood \(N(x)\) contains an independent set of three vertices. If \(G\) is claw-free, then for any two vertices \(x\), \(y\) at distance two in \(G\) there exists a common neighbor \(u\) such that \(N(u)\subseteq\{x, y\}\cup N(x)\cup N(y)\). A graph with the latter property is called quasi-claw-free. The author shows that a quasi-claw-free 3-connected graph \(G\) on \(n\) vertices and with minimum degree \(\delta\) has a Hamiltonian cycle, if \(\delta\geq{n+ 5\over 5}\). For claw-free graphs this was first shown by \textit{M. Li} [Hamiltonian cycles in 3-connected claw-free graphs, J. Graph Theory 17, No. 3, 303--313 (1993; Zbl 0778.05056)]. The proof is along similar lines.