Premium
Generalized degree conditions for graphs with bounded independence number
Author(s) -
Faudree Ralph,
Gould Ronald J.,
Lesniak Linda,
Lindquester Terri
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190190312
Subject(s) - combinatorics , mathematics , bounded function , independence number , upper and lower bounds , graph , bound graph , connectivity , discrete mathematics , hamiltonian (control theory) , cardinality (data modeling) , degree (music) , graph power , line graph , physics , data mining , mathematical analysis , mathematical optimization , computer science , acoustics
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.