On hamiltonicity of P3-dominated graphs |
| |
| Authors: | H. J. Broersma E. Vumar |
| |
| Affiliation: | (1) Center for Combinatorics, Nankai University, 300071 Tianjin, People’s Republic of China;(2) Present address: Department of Computer Science, Durham University, Science Labs, South Road, Durham, DH1 3LE, UK;(3) College of Mathematics and Systems Science, Xinjiang University, 830046 Urumqi, People’s Republic of China |
| |
| 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 α(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. This paper was completed when both authors visited the Center for Combinatorics, Nankai University, Tianjin. They gratefully acknowledge the hospitality and support of the Center for Combinatorics and Nankai University. The work of E.Vumar is sponsored by SRF for ROCS, REM. |
| |
| Keywords: | Claw-free graph Quasi-claw-free graph Hamiltonian cycle P 3-dominated graph |
| 本文献已被 SpringerLink 等数据库收录！ |
|
