Graphs without repeated cycle lengths

Abstract

In 1975, P. Erdös 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)\ge n+36t$$ for $t=1260r+169(r\ge 1)$ and $n\ge 540t^2+175811/2t+7989/2$. Consequently, $\liminf\sb {n \to \infty} {f(n)-n \over \sqrt n} \geq \sqrt {2 + {2 \over 5}}.$ We make the following conjecture: \par \bigskip \noindent{\bf Conjecture.} $$\underset{n\to \infty }{\lim }\frac{f(n)-n}{\sqrt{n}}=\sqrt{2.4}.$$

5 pages