Hamiltonicity of Regular 2-Connected Graphs

Let G be a k-regular 2-connected graph of order n. Jackson proved that G is hamiltonian if n 5 3k. Zhu and Li showed that the upper bound 3k on n can be relaxed to q k if G is 3-connected and k 2 63. We improve both results by showing that G is hamiltonian if n 5 gk- 7 and G does not belong to a restricted class 3 of nonhamiltonian graphs of connectivity 2. To establish this result we obtain a variation of Woodall's Hopping Lemma and use it to prove that if n 5 $ k- 7 and G has a dominating cycle (i.e., a cycle such that the vertices off the cycle constitute an independent set), then G is hamiltonian. We also prove that if n 5 4k- 3 and G $ 3, then G has a dominating cycle. For k 2 4 it is conjectured that G is hamiltonian if n 5 4k and G $ 3. 0 1996 John Wiley & Sons, Inc