On hamiltonicity of P 3 -dominated graphs

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 α(G 2 ) ≤ κ(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)| ≤ 5δ(G) − 5. These results extend known results on (quasi-)claw-free graphs. Copyright Springer-Verlag 2009

MoreLess

Year of publication:	2009
Authors:	Broersma, H. ; Vumar, E.
Published in:	Computational Statistics. - Springer. - Vol. 69.2009, 2, p. 297-306
Publisher:	Springer
Subject:	Claw-free graph \| Quasi-claw-free graph \| Hamiltonian cycle \| P 3 -dominated graph

More details

Extent:	text/html
Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10010847834