GENERALIZED DEGREE CONDITIONS FOR GRAPHS WITH BOUNDED INDEPENDENCE NUMBER

We consider a generalized degree condition based on the cardinality of the neighborhood union of arbitrary sets of r vertices. We show that a Dirac-type bound on this degree in conjunction with a bound on the i ndependence number of a graph is sufficient to imply certain hamiltoni an properties in graphs. For K-1,K-m-free graphs we obtain generalizat ions of known results. in particular we show: Theorem. Let r greater t han or equal to 1 and m greater than or equal to 3 be integers. Then f or each nonnegative function f(r, m) there exists a constant C = C(r, m, f(r, m)) such that if G is a graph of order n (n greater than or eq ual to r, n > m) with delta(r)(G) greater than or equal to (n/3) + C a nd beta(G) less than or equal to f(r, m), then (a) G is traceable if d elta(G) greater than or equal to r and G is connected; (b) G is hamilt onian if delta(G) greater than or equal to r + 1 and G is 2-connected; (c) G is hamiltonian-connected if delta(G) greater than or equal to r + 2 and Gis S-connected. (C) 1995 John Wiley & Sons, Inc.