Generalized degree conditions for graphs with bounded independence number
Ralph J. Faudree, Ronald J. Gould, Linda M. Lesniak, Terri Lindquester · Journal of Graph Theory · 1995
Abstract 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 independence number of a graph is sufficient to imply certain hamiltonian properties in graphs. For K 1,m ‐free grphs we obtain generalizations of known results. In particular we show: Theorem. Let r ≥ 1 and m ≥ 3 be integers. Then for 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 ≥ r, n > m) with δ r ( G ) ≥ ( n /3) + C and β ( G ) ≥ f(r, m ), then (a) G is traceable if δ( G ) ≥ r and G is connected; (b) G is hamiltonian if δ( G ) ≥ r + 1 and G is 2‐connected; (c) G is hamiltonian‐connected if δ( G ) ≥ r + 2 and G is 3‐connected. © 1995 John Wiley & Sons, Inc.