### Abstract

Original language | Undefined |
---|---|

Article number | 10.1007/s00186-008-0260-7 |

Pages (from-to) | 297-306 |

Number of pages | 10 |

Journal | Mathematical methods of operations research |

Volume | 69 |

Issue number | 2 |

DOIs | |

Publication status | Published - May 2009 |

### Keywords

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

### Cite this

_{3}-dominated graphs.

*Mathematical methods of operations research*,

*69*(2), 297-306. [10.1007/s00186-008-0260-7]. https://doi.org/10.1007/s00186-008-0260-7

}

_{3}-dominated graphs'

*Mathematical methods of operations research*, vol. 69, no. 2, 10.1007/s00186-008-0260-7, pp. 297-306. https://doi.org/10.1007/s00186-008-0260-7

**On hamiltonicity of P _{3}-dominated graphs.** / Broersma, Haitze J.; Vumar, E.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - On hamiltonicity of P3-dominated graphs

AU - Broersma, Haitze J.

AU - Vumar, E.

N1 - 10.1007/s00186-008-0260-7

PY - 2009/5

Y1 - 2009/5

N2 - 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.

AB - 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.

KW - METIS-263700

KW - EWI-14302

KW - IR-67623

U2 - 10.1007/s00186-008-0260-7

DO - 10.1007/s00186-008-0260-7

M3 - Article

VL - 69

SP - 297

EP - 306

JO - Mathematical methods of operations research

JF - Mathematical methods of operations research

SN - 1432-2994

IS - 2

M1 - 10.1007/s00186-008-0260-7

ER -

_{3}-dominated graphs. Mathematical methods of operations research. 2009 May;69(2):297-306. 10.1007/s00186-008-0260-7. https://doi.org/10.1007/s00186-008-0260-7