Graphs without repeated cycle lengths
by
Chunhui Lai
Zhangzhou Teachers College

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 problem of determining f(n) (see J.A. Bondy and U.S.R. Murty [Graph Theory with Applications (Macmillan, New York, 1976)], p.247, Problem 11). Y. Shi [ Discrete Math. 71(1988) 57-71] proved that

f(n) ≥ n+ [( Ö   8n-23   +1)/2]

for n ≥ 3. E. Boros, Y. Caro, Z. Füredi and R. Yuster [ Journal of Combinatorial Theory, Series B 82(2001), 270-284.] proved that

f(n) ≤ n+1.98√n(1+o(1)).

Chunhui Lai [ Australasian Journal of Combinatorics 27(2003), 101-105.] proved that

liminf n → ∞  f(n)-n √n ≥ Ö   2.4   .

and conjectured that

lim n → ∞  f(n)-n √n = Ö   2.4   .

We think it is difficult to prove this conjecture. It would be nice to prove the following conjecture:

Conjecture [Chunhui Lai, Discrete Math. 122(1993) 363-364.].

liminf n → ∞  f(n)-n √n ≤ √3.

Date received: February 13, 2008