On hamiltonicity of P3-dominated graphs

Broersma, H.J.; Vumar, E.

Abstract

We introduce a new class of graphs which we call P₃-dominated graphs. This class properly contains all quasi-claw-free graphs, and hence all claw-free graphs. Let G be a 2-connected P₃-dominated graph. We prove that G is hamiltonian if α(G²) ≤ κ(G), with two exceptions: K₂,₃ and K₁,₁,₃. We also prove that G is hamiltonian, if G is 3-connected and |V(G)| ≤ 5δ(G) − 5. These results extend known results on (quasi-)claw-free graphs.

Citation

Broersma, H., & Vumar, E. (2009). On hamiltonicity of P3-dominated graphs. Mathematical Methods of Operations Research, 69(2), 297-306. https://doi.org/10.1007/s00186-008-0260-7

• Journal Article Type: Article
• Publication Date: May 1, 2009
• Deposit Date: Mar 1, 2010
• Journal: Mathematical Methods of Operations Research
• Print ISSN: 1432-2994
• Electronic ISSN: 1432-5217
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 69
• Issue: 2
• Pages: 297-306
• DOI: https://doi.org/10.1007/s00186-008-0260-7
• Keywords: Claw-free graph, Quasi-claw-free graph, Hamiltonian cycle, P₃-dominated graph.
• Public URL: https://durham-repository.worktribe.com/output/1523359