On the Number of Cycles in a Graph with Restricted Cycle Lengths

Abstract: Let

L

be a set of positive integers. We call a (directed) graph

G

an

L

emph{-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

v e c 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) = T h e t a_{L} (n^{l f l o o r k / e l l f l o o r})

where

k

is the largest element of

L

and

2 e l l

is the smallest even element of

L

(if

L

contains only odd elements, then

c (L, n) = T h e t a_{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

v e c c (L, n) = (1 + o (1)) (f r a c n - 1 k - 1)^{k - 1}

, where

k

is the largest element of

L

. We determine the exact value of

v e c c (k, n)

for every

k

and characterize all graphs attaining this maximum.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: On the Number of Cycles in a Graph with Restricted Cycle Lengths