Abstract:
In 1975, P. Erd H os proposed the problem of determining the maximum number $f(n)$ of edges in a graph with $n$ vertices in which any two cycles are of different lengths. The sequence $(c_1,c_2, cdots,c_n)$ is the cycle length distribution of a graph $G$ with $n$ vertices, where $c_i$ is the number of cycles of length $i$ in $G$. Let $f(a_1,a_2, cdots,$$a_n)$ denote the maximum possible number of edges in a graph which satisfies $c_i leq a_i$, where $a_i$ is a nonnegative integer. In 1991, Shi posed the problem of determining $f(a_1,a_2, cdots,a_n),$ which extended the problem due to Erd H os. It is clear that $f(n)=f(1,1, cdots,1)$.Let $g(n,m)=f(a_1,a_2, cdots,a_n),$ where $a_i=1$ if $i/m$ is an integer, and $a_i=0$ otherwise.It is clear that $f(n)=g(n,1)$.We prove that $ liminf sb {n to infty} {f(n)-n over sqrt n} geq sqrt {2 + frac{40}{99}},$ which is better than the previous bounds $ sqrt 2$ (Shi, 1988), and $ sqrt {2 + frac{7654}{19071}}$ (Lai, 2017).We show that $ liminf_{n rightarrow infty} {g(n,m)-n over sqrt frac{n}{m}} > sqrt {2.444},$ for all even integers $m$. We make the following conjecture:$ liminf sb {n to infty} {f(n)-n over sqrt n} > sqrt {2.444}.$ par