On hamiltonicity of $P_3$-dominated graphs

Share/Save/Bookmark

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

[img]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:
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

 

Repository Staff Only: item control page