Graphs without repeated cycle lengths

2003/05/12 by Chunhui Lai
Mathematics · #math.CO #msc:05C38 #msc:05C35

paper · pdf

published as Australasian Journal of Combinatorics 27 2003 101-105 · 5 pages

arxiv created 2003/05/12 · arxiv updated 2009/11/30

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)≥ n+36t for t=1260r+169 (r≥ 1) and n ≥ 540t²+175811/2t+7989/2. Consequently, \liminf\sb n → ∞ f(n)-n \over √ n ≥ √ 2 + 2 \over 5. We make the following conjecture: \par \bigskip \noindent\bf Conjecture. lim_{n → ∞} f(n)-n\over √ n=√ 2.4.

Related

• A Lower Bound for the Number of Edges in a Graph Containing No Two Cycles of the Same Length
• Upper bounds on the extremal number of the 4-cycle
• Non-repeated cycle lengths and Sidon sequences
• Cycle lengths and chords under chromatic and degree constraints
• Longest Cycle above Erdős-Gallai Bound