NEIGHBORHOOD UNIONS AND HAMILTON CYCLES

Let G be a graph on n vertices and N2(G) denote the minimum size of N(u) union N(upsilon) taken over all pairs of independent vertices u, upsilon of G. We show that if G is 3-connected and N2(G) greater-than-or-equal-to 1/2(n + 1), then G has a Hamilton cycle. We show further that if G is 2-connected and N2(G) greater-than-or-equal-to 1/2 (n + 3), then either G has a Hamilton cycle or else G belongs to one of three families of exceptional graphs.