On hamiltonicity of P3-dominated graphs

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)


We introduce a new class of graphs which we call $P_3$-dominated graphs. This class properly contains all quasi-claw-free graphs, and hence all claw-free graphs. Let $G$ be a 2-connected $P_3$-dominated graph. We prove that $G$ is hamiltonian if $\alpha(G^2)\le \kappa(G)$, with two exceptions: $K_{2,3}$ and $K_{1,1,3}$. We also prove that $G$ is hamiltonian, if $G$ is 3-connected and $|V(G)| \le 5\delta(G) - 5$. These results extend known results on (quasi-)claw-free graphs.
Original languageUndefined
Article number10.1007/s00186-008-0260-7
Pages (from-to)297-306
Number of pages10
JournalMathematical methods of operations research
Issue number2
Publication statusPublished - May 2009


  • METIS-263700
  • EWI-14302
  • IR-67623

Cite this