Some Extremal Problems on the Cycle Length Distribution of Graphs

The cycle length distribution (CLD) of a graph of order \(n\) is \((c_1, c_2, \ldots, c_n)\), where \(c_i\) is the number of cycles of length \(i\), for \(i = 1, 2, \ldots, n\). For an integer sequence \((a_1, a_2, \ldots, 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, \ldots, c_n)\) such that \(c_i \geq a_i\) for \(i = 1, 2, \ldots, n\). The number of edges in such a graph is denoted by \(g(a_1, a_2, \ldots, a_n)\). In this paper, we give the lower and upper bounds of \(g(0, 0, k, \ldots, k)\) for \(k = 2, 3, 4\).