MathSciDoc: An Archive for Mathematician ∫

Let $f(n)$ be the maximum number of edges in a graph on $n$ vertices in which no two cycles have the same length. In 1975, Erdős raised the question of determining $f(n)$ [see J. A. Bondy and U. S. R. Murty, Graph theory with applications, Elsevier, New York, 1976; MR0411988 (54 #117)]. We prove that for $n\geq 36\cdot 5t^2-4\cdot 5t+1$ one has $f(n)\geq n+9t-1$ . We conjecture that $\liminf (f(n)-n)/\sqrt n\leq\sqrt 3$ .

maximum number of edges; graph; cycle