HAMILTONIAN GRAPHS WITH NEIGHBORHOOD INTERSECTIONS

In this paper, k + 1 real numbers c1, c2, ..., c(k+1) are found such t hat the following condition is sufficient for a k-connected graph of o rder n to be hamiltonian: for each independent vertex set of k + 1 ver tices in G c1\Si\ + c2\S2\ + ... + c(k+1)\S(k+1)\ > n-1, where S(i) = {v is-an-element-of V: \N(v) and S\ = i} for 0 less-than-or-equal-to i less-than-or-equal-to k + 1. Such a set of k + 1 numbers is called an Hk-sequence. A sufficient condition for the existence of Hk-sequences is obtained that generalizes many known results involving sum of degr ees, neighborhood unions, and/or neighborhood intersections. (C) 1994 John Wiley & Sons, Inc.