We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

On hamiltonicity of P₃-dominated graphs.

Broersma, H. J. and Vumar, E. (2009) 'On hamiltonicity of P₃-dominated graphs.', Mathematical methods of operations research., 69 (2). pp. 297-306.


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.

Item Type:Article
Keywords:Claw-free graph, Quasi-claw-free graph, Hamiltonian cycle, P₃-dominated graph.
Full text:Full text not available from this repository.
Publisher Web site:
Record Created:01 Mar 2010 13:05
Last Modified:08 Dec 2010 11:57

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Look up in GoogleScholar | Find in a UK Library