On hamiltonicity of $P_3$ -dominated graphs

Broersma, H.J. and Vumar, E. (2009) On hamiltonicity of $P_3$ -dominated graphs. Mathematical methods of operations research, 69 (2). pp. 297-306. ISSN 1432-2994

PDF
Restricted to UT campus only: Request a copy
164Kb

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.
Item Type:	Article
Copyright:	© 2009 Springer
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/67623
Official URL:	http://dx.doi.org/10.1007/s00186-008-0260-7
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

On hamiltonicity of -dominated graphs

On hamiltonicity of $P_3$ -dominated graphs