On weights of induced paths and cycles in claw-free and K-1,K-r-free graphs

Let G be a K-1,K-r-free graph (r greater than or equal to 3) on n vertices. We prove that, for any induced path or induced cycle on k vertices in G(k greater than or equal to 2r-1 or k greater than or equal to 2r, respectivel y), the degree sum of its vertices is at most (2r - 2)(n - alpha) where ci is the independence number of G. As a corollary we obtain an upper bound on the length of a longest induced path and a longest induced cycle in a K-1, K-r-free graph. Stronger bounds are given in the special case of claw-free graphs (i.e., r = 3). Sharpness examples are also presented. (C) 2001 John Wiley & Sons. Inc.