On the size of graphs without repeated cycle lengths

Chunhui Lai

Published 2016-12-19Version 1

In 1975, P. Erd\"os proposed the problem of determining the maximum number $f(n)$ of edges in a graph of $n$ vertices in which any two cycles are of different lengths. In this paper, it is proved that $$f(n)\geq n+\frac{107}{3}t+\frac{7}{3}$$ for $t=1260r+169 \,\ (r\geq 1)$ and $n \geq \frac{2119}{4}t^{2}+87978t+\frac{15957}{4}$. Consequently, $\lim \inf_{n \to \infty} {f(n)-n \over \sqrt n} \geq \sqrt {2 + \frac{7654}{19071}},$ which is better than the previous bounds $\sqrt 2$ [Y. Shi, Discrete Math. 71(1988), 57-71], $\sqrt {2.4}$ [C. Lai, Australas. J. Combin. 27(2003), 101-105]. The conjecture $\lim_{n \rightarrow \infty} {f(n)-n\over \sqrt n}=\sqrt {2.4}$ is not true.