LONG CYCLES, DEGREE SUMS AND NEIGHBORHOOD UNIONS

For a graph G, define the parameters alpha(G) = max{\S\\S is an indepe ndent set of vertices of G}, sigma(k)(G) = min{SIGMA(i=1)k d(v(i)\{v1, ...,v(k)} is an independent set} and NC(k)(G) = min {or(i=1)k N(v(i))\ \{v1,...,v(k)} is an independent set} (k greater-than-or-equal-to 2). It is shown that every 1-tough graph G of order n greater-than-or-equa l-to 3 with sigma3(G) greater-than-or-equal-to n+r greater-than-or-equ al-to n has a cycle of length at least min{n,n+NC(r+5+epsilon(n+r))(G) -alpha(G)}, where epsilon(i)=3([1/3i]-1/3i). This result extends previ ous results in Bauer et al. (1989/90), Fassbender(1992) and Flandrin e t al. (1991). It is also shown that a 1-tough graph G of order n great er-than-or-equal-to 3 with sigma3(G) greater-than-or-equal-to n+r grea ter-than-or-equal-to n has a cycle of length at least min{n,2NC[1/8(n6r+17)](G)}. Analogous results are established for 2-connected graphs.