On hamiltonicity of P3-dominated graphs

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)

Abstract

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
Volume69
Issue number2
DOIs
Publication statusPublished - May 2009

Keywords

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

Cite this

@article{837ee514b4dd47efbb2054e3d1e6c134,
title = "On hamiltonicity of P3-dominated graphs",
abstract = "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.",
keywords = "METIS-263700, EWI-14302, IR-67623",
author = "Broersma, {Haitze J.} and E. Vumar",
note = "10.1007/s00186-008-0260-7",
year = "2009",
month = "5",
doi = "10.1007/s00186-008-0260-7",
language = "Undefined",
volume = "69",
pages = "297--306",
journal = "Mathematical methods of operations research",
issn = "1432-2994",
publisher = "Physica-Verlag",
number = "2",

}

On hamiltonicity of P3-dominated graphs. / Broersma, Haitze J.; Vumar, E.

In: Mathematical methods of operations research, Vol. 69, No. 2, 10.1007/s00186-008-0260-7, 05.2009, p. 297-306.

Research output: Contribution to journalArticleAcademicpeer-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 -