Some Extremal Problems on the Cycle Length Distribution of Graphs

Abstract

The cycle length distribution (CLD) of a graph of order $n$ is $(c_1,c_2,\dots ,c_n)$, where $c_i$ is the number of cycles of length $i$, for $i=1,2,\dots ,n$. For an integer sequence $(a_1,a_2,\dots ,a_n)$, we consider the problem of characterizing those graphs $G$ with the minimum possible edge number and with $\text{CLD}(G)=(c_1,c_2,\dots ,c_n)$ such that $c_i\ge a_i$ for $i=1,2,\dots ,n$. The number of edges in such a graph is denoted by $g(a_1,a_2,\dots ,a_n)$. In this paper, we give the lower and upper bounds of $g(0,0,k,\dots ,k)$ for $k=2,3,4$.