| Abstract: | Let G be a k-regular 2-connected graph of order n. Jackson proved that G is hamiltonian if n ≤ 3k. Zhu and Li showed that the upper bound 3k on n can be relaxed to 22/7k if G is 3-connected and k ≥ 63. We improve both results by showing that G is hamiltonian if n ≤ 7/2k − 7 and G does not belong to a restricted class F 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 ≤ 7/2k − 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 ≤ 4k − 3 and G ∉ F, then G has a dominating cycle. For k ≥ 4 it is conjectured that G is hamiltonian if n ≤ 4k and G ∉ F. © 1996 John Wiley & Sons, Inc. |
