Hamiltonian graphs involving neighborhood unions

Dirac proved that a graph G is hamiltonian if the minimum degree $\delta(G) \geq n/2$ , where n is the order of G . Let G be a graph and $A \subseteq V(G)$ . The neighborhood of A is $N(A)=\{ b: ab \in E(G)$ for some $a \in A\}$ . For any positive integer k , we show that every (2 k  − 1)‐connected graph of order n  ≥ 16 k 3 is hamiltonian if | N ( A )| ≥  n /2 for every independent vertex set A of k vertices. The result contains a few known results as special cases. The case of k  = 1 is the classic result of Dirac when n is large and the case of k  = 2 is a result of Broersma, Van den Heuvel, and Veldman when n is large. For general k , this result improves a result of Chen and Liu. The lower bound 2 k  − 1 on connectivity is best possible in general while the lower bound 16 k 3 for n is conjectured to be unnecessary. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 83–100, 2006