标题： 图中限制循环长度的循环数量 显示英文标题

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

摘要： 设$L$为一组正整数。 我们称一个（有向）图$G$为$L$\emph{-环图} ，如果$G$中的所有环长度都属于$L$。 设$c(L,n)$为一个$n$顶点的$L$-环图中可能的最大环数（我们用$\vec{c}(L,n)$表示有向图中的环数）。 在无向情况下，我们证明对于任何固定的集合$L$，我们有$c(L,n)=\Theta_L(n^{\lfloor k/\ell \rfloor})$，其中$k$是$L$中的最大元素，而$2\ell$是$L$中的最小偶数元素（如果$L$仅包含奇数元素，则$c(L,n)=\Theta_L(n)$成立。） 我们还给出了当$L$是单个元素时$L$-循环图的特征。 在有向情况下，我们证明了对于任何固定的集合$L$，我们有 $\vec{c}(L,n)=(1+o(1))(\frac{n-1}{k-1})^{k-1}$，其中$k$是$L$中的最大元素。 我们确定了$\vec{c}(\{k\},n)$对于每个$k$的精确值，并表征了所有达到此最大值的图。 显示英文摘要

摘要： 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 $\vec{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)=\Theta_L(n^{\lfloor k/\ell \rfloor})$ where $k$ is the largest element of $L$ and $2\ell$ is the smallest even element of $L$ (if $L$ contains only odd elements, then $c(L,n)=\Theta_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 $\vec{c}(L,n)=(1+o(1))(\frac{n-1}{k-1})^{k-1}$, where $k$ is the largest element of $L$. We determine the exact value of $\vec{c}(\{k\},n)$ for every $k$ and characterize all graphs attaining this maximum.