# MathSciDoc: An Archive for Mathematician ∫

#### Combinatoricsmathscidoc:1711.06001

Discrete Applied Mathematics, 232, 226-229, 2017.12
In 1975, P. Erd\"{o}s 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. 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, $\liminf\sb {n \to \infty} {f(n)-n \over \sqrt n} \geq \sqrt {2 + \frac{7654}{19071}},$ which is better than the previous bounds $\sqrt 2$ (Shi, 1988), $\sqrt {2.4}$ (Lai, 2003). The conjecture $\lim_{n \rightarrow \infty} {f(n)-n\over \sqrt n}=\sqrt {2.4}$ is not true.
graph, cycle, number of edges
@inproceedings{lai2017on,
title={On the size of graphs without repeated cycle lengths},
author={Lai Chunhui},
url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20171107083336050698849},
booktitle={Discrete Applied Mathematics},
volume={232},
pages={226-229},
year={2017},
}

Lai Chunhui. On the size of graphs without repeated cycle lengths. 2017. Vol. 232. In Discrete Applied Mathematics. pp.226-229. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20171107083336050698849.