NEIGHBORHOOD UNIONS AND THE CYCLE COVER NUMBER OF A GRAPH

For several years, the study of neighborhood unions of graphs has give n rise to important structural consequences of graphs. In particular, neighborhood conditions that give rise to hamiltonian cycles have been considered in depth. In this paper we generalize these approaches to give a bound on the smallest number of cycles in G containing all the vertices of G. We show that if for all x, y is-an-element-of V(G), \N( x) U N(y)\ greater-than-or-equal-to 2n/5 + 1, then V(G) is coverable b y at most two cycles. Several related results and extensions to t cycl es are also given. (C) 1994 John Wiley & Sons Inc.