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 less than or equal to 3k. Zhu and Li showed tha t the upper bound 3k on n can be relaxed to 22/7k if G is 3-connected and k greater than or equal to 63. We improve both results by showing that G is hamiltonian if n less than or equal to 7/2k - 7 and G does n ot belong to a restricted class F of nonhamiltonian graphs of connecti vity 2. To establish this result we obtain a variation of Woodall's Ho pping Lemma and use it to prove that if n less than or equal to 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. W e also prove that if n less than or equal to 4k - 3 and G is not an el ement of F, then G has a dominating cycle. For k greater than or equal to 4 it is conjectured that G is hamiltonian if n less than or equal to 4k and G is not an element of F. (C) 1996 John Wiley & Sons, Inc.