Hamiltonian graphs involving neighborhood unions
Guantao Chen, Warren E. Shreve, Bing Wei · Journal of Graph Theory · 2006
Abstract 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 (2k − 1)‐connected graph of order n ≥ 16k3 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 2k − 1 on connectivity is best possible in general while the lower bound 16k3 for n is conjectured to be unnecessary. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 83–100, 2006