A Lower Bound for the Number of Edges in a Graph Containing No Two Cycles of the Same Length

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+32t-1$$ for $t=27720r+169(r\ge 1)$ and $n\ge 6911/16t^2+514441/8t-3309665/16$. Consequently, $\liminf\sb {n \to \infty} {f(n)-n \over \sqrt n} \geq \sqrt {2 + {2562 \over 6911}}.$

6 pages