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 intersect ions 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 int ersections, we prove the following theorem. Thorem. Let G be a graph o f 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 ca rdinality 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 Sigm a(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 vertic es whose nearest vertex in X is at distance j. This theorem improves o r generalizes many well-known sufficient conditions for hamiltonian gr aphs. (C) 1995 John Wiley & Sons, Inc.