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

2002/06/07 by Chunhui Lai
Mathematics · #math.CO #msc:05C38 #msc:05C35

paper · pdf

published as The Electronic Journal of Combinatorics 8(2001), #N9 · 6 pages

arxiv created 2002/06/07 · 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+32t-1 for t=27720r+169 (r≥ 1) and n≥6911/16t²+514441/8t-3309665/16. Consequently, \liminf\sb n → ∞ f(n)-n \over √ n ≥ √ 2 + 2562 \over 6911.

Related

• Graphs without repeated cycle lengths
• Upper bounds on the extremal number of the 4-cycle
• Non-repeated cycle lengths and Sidon sequences
• On graphs without cycles of length 1 modulo 3
• The maximum number of cliques in graphs without long cycles