2018/10/11 by Daza, David Fernando, Trujillo, Carlos Alberto, Benavides, Fenando Andrés · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1810.05262
The problem of determining the Turán number of C4 is a well studied problem that dates back to a paper of Erdös from 1938. It is known that Sidon sets can be used to construct C4-free graphs. If \A is a Sidon set in the abelian group X, the sum graph GX, \A with vertex set X and edges set E=\\x, y\:x≠ y, x+y∈ \A\ is C4-free. Using the sum graph of a Sidon set of type Singer we verify a conjecture of Erdös and Simonovits concerning the number of copies of C4 in a graph with ex(q2+q+1, C4)+1 edges. Further, we give a sufficient condition for the sum graph of a Sidon set to be C4-saturated and describe new C4-saturated graphs.