2016/10/11 by Gerbner, Dániel, Keszegh, Balázs, Palmer, Cory +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1610.03476
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)=ΘL(n\lfloor k/ℓ \rfloor) 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)=ΘL(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(\k\,n) for every k and characterize all graphs attaining this maximum.