ON THE NUMBER OF CYCLES IN A GRAPH WITH RESTRICTED CYCLE LENGTHS.

Let L be a set of positive integers. We call a (directed) graph G an L-cycle graph if all cycle lengths in G belong to L. Let c(L; n) be the maximum number of cycles possible in an n-vertex L-cycle graph (we use ~c(L; n) for the number of cycles in directed graphs). In the undirected case we show that for any fixed set L, we have c(L; n) = (nbk=`c), where k is the largest element of L and 2` is the smallest even element of L (if L contains only odd elements, then c(L; n) = (n) holds). We also give a characterization of L-cycle graphs when L is a single element. In the directed case we prove that for any fixed set L, we have ~c(L; n) = (1 + o(1))( n 1 k 1 ) k 1, where k is the largest element of L. We determine the exact value of ~c(fkg; n) for every k and characterize all graphs attaining this maximum. [ABSTRACT FROM AUTHOR]