INSERTIBLE VERTICES, NEIGHBORHOOD INTERSECTIONS, AND HAMILTONICITY

Let G be a simple undirected graph of order n. For an independent set S subset of V(G) of k vertices, we define the k neighborhood intersections S-i = {v is an element of V(G)\S\\N(v)boolean AND S\ = i}, 1 less than or equal to i less than or equal to k, with s(i) = \S-i\. Using the concept of insertible vertices and the concept of neighborhood intersections, we prove the following theorem. Thorem. Let G be a graph of order n and connectivity kappa greater than or equal to 2. Then G is hamiltonian or there exists an independent set X subset of V(G) of cardinality t + 1, 1 less than or equal to t less than or equal to kappa such that [GRAPHICS] where w(i), 1 less than or equal to i less than or equal to t + 1, are real numbers satisfying 0 less than or equal to w(1) less than or equal to 1, and for 1 < i(1) less than or equal to i(2)...less than or equal to i(m) less than or equal to t + 1 and Sigma(j=1)(m), i(j) less than or equal to t + 1 we have Sigma(j=1)(m)(Wj(i) - 1) less than or equal to 1; where N-j(X) denotes the set of vertices whose nearest vertex in X is at distance j. This theorem improves or generalizes many well-known sufficient conditions for hamiltonian graphs. (C) 1995 John Wiley & Sons, Inc.