TY - JOUR

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

AU - Gerbner, Dániel

AU - Keszegh, Balázs

AU - Palmer, Cory

AU - Patkós, Balázs

N1 - Funding Information:
∗Received by the editors October 14, 2016; accepted for publication (in revised form) July 19, 2017; published electronically January 30, 2018. http://www.siam.org/journals/sidma/32-1/M109898.html Funding: The first and second authors’ research supported by the János Bolyai Research Fellowship of the Hungarian Academy of Sciences and the National Research, Development and Innovation Office–NKFIH under grants PD 109537 and K 116769. The third author’s research was supported by University of Montana UGP grant M25364. The fourth author’s research was supported by the János Bolyai Research Fellowship of the Hungarian Academy of Sciences and in part by the National Research, Development, and Innovation Office–NKFIH under grant SNN 116095.
Publisher Copyright:
© 2018 Society for Industrial and Applied Mathematics.

PY - 2018

Y1 - 2018

N2 - 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 )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.

AB - 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 )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.

KW - Cycles

KW - Directed graphs

KW - Extremal problems

UR - http://www.scopus.com/inward/record.url?scp=85045690379&partnerID=8YFLogxK

U2 - 10.1137/16M109898X

DO - 10.1137/16M109898X

M3 - Article

AN - SCOPUS:85045690379

SN - 0895-4801

VL - 32

SP - 266

EP - 279

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -