Non-repeated cycle lengths and Sidon sequences

2020/07/24 by Ma, Jie, Yang, Tianchi
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2007.12513

Abstract

We prove a conjecture of Boros, Caro, Füredi and Yuster on the maximum number of edges in a 2-connected graph without repeated cycle lengths, which is a restricted version of a longstanding problem of Erdős. Our proof together with the matched lower bound construction of Boros, Caro, Füredi and Yuster show that this problem can be conceptually reduced to the seminal problem of finding the maximum Sidon sequences in number theory.

Related

• Graphs without repeated cycle lengths
• Sidon Sets and graphs without 4-cycles
• A Lower Bound for the Number of Edges in a Graph Containing No Two Cycles of the Same Length
• The maximum number of cliques in graphs without long cycles
• Upper bounds on the extremal number of the 4-cycle