## Abstract

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) = Θ(nk/), 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}_{k−}^{−}_{1}^{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.

Original language | English |
---|---|

Pages (from-to) | 266-279 |

Number of pages | 14 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 32 |

Issue number | 1 |

DOIs | |

State | Published - 2018 |

## Keywords

- Cycles
- Directed graphs
- Extremal problems