On the number of cycles in a graph with restricted cycle lengths

Dániel Gerbner, Balázs Keszegh, Cory Palmer, Balázs Patkós

Research output: Contribution to journalArticlepeer-review

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))(nk−11 )k1, 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 languageEnglish
Pages (from-to)266-279
Number of pages14
JournalSIAM Journal on Discrete Mathematics
Volume32
Issue number1
DOIs
StatePublished - 2018

Keywords

  • Cycles
  • Directed graphs
  • Extremal problems

Fingerprint

Dive into the research topics of 'On the number of cycles in a graph with restricted cycle lengths'. Together they form a unique fingerprint.

Cite this