On the size of 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+\frac{107}{3}t+\frac{7}{3}$$ for $t=1260r+169(r\ge 1)$ and $n\ge \frac{2119}{4}{t}^2+87978t+\frac{15957}{4}$. Consequently, $\lim {\inf }_{n\to \infty }\frac{f(n)-n}{\sqrt{n}}\ge \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\to \infty }\frac{f(n)-n}{\sqrt{n}}=\sqrt{2.4}$ is not true.

7 pages

Cited by in corpus (2)

• On the number of edges in some graphs
• An old problem of Erdős: a graph without two cycles of the same length