HAMILTONIAN PROPERTIES OF GRAPHS WITH LARGE NEIGHBORHOOD UNIONS

Let G be a graph of order n, sigma(k) = min {SIGMA(i = 1)k d(upsilon(i)): {upsilon-1,..., upsilon(k)] is an independent set of vertices in G}, NC = min{\N(u) or N(upsilon)\: u-upsilon is-not-an-element-of E(G)} and NC2 = min {\N(u) or N(upsilon)\: d(u, upsilon) = 2}. Ore proved that G is hamiltonian if sigma-2 greater-than-or-equal-to n greater-than-or-equal-to 3, while Faudree et al. proved that G is hamiltonian if G is 2-connected and NC greater-than-or-equal-to 1/3 (2n - 1). It is shown that both results are generalized by a recent result of Bauer et al. Various other existing results in hamiltonian graph theory involving degree-sums or cardinalities of neighborhood unions are also compared in terms of generality. Furthermore, some new results are proved. In particular, it is shown that the bound 1/3(2n - 1) on NC in the result of Faudree et al. can be lowered to 1/3(2n - 3), which is best possible. Also, G is shown to have a cycle of length at least min{n, 2(NC2)} if G is 2-connected and sigma-3 greater-than-or-equal-to n + 2. A D(lambda)-cycle (D(lambda)-path) of G is a cycle (path) C such that every component of G - V(C) has order smaller than lambda. Sufficient conditions of Lindquester for the existence of Hamilton cycles and paths involving NC2 are extended to D(lambda)-cycles and D(lambda)-paths.