Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.


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.

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.

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:http://dx.doi.org/10.1007/s00186-008-0260-7
Record Created:01 Mar 2010 13:05
Last Modified:08 Dec 2010 11:57

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