Sidon sets and graphs without 4-cycles

DOI10.4310/JOC.2014.V5.N2.A1zbMATH Open1304.05078arXiv1309.6350OpenAlexW2962886144MaRDI QIDQ477968FDOQ477968

Authors: Michael Tait, Craig Timmons 

Publication date: 10 December 2014

Published in: Journal of Combinatorics (Search for Journal in Brave)

Abstract: The problem of determining the maximum number of edges in an $n$-vertex graph that does not contain a 4-cycle has a rich history in extremal graph theory. Using Sidon sets constructed by Bose and Chowla, for each odd prime power $q$ we construct a graph with $q^2-q-2$ vertices that does not contain a 4-cycle and has at least $frac12q^3-q^2-O(q^{3/4})$ edges. This disproves a conjecture of Abreu, Balbuena, and Labbate concerning the Tur'{a}n number $mathrmex(q^2-q-2,C_4)$.

Full work available at URL: https://arxiv.org/abs/1309.6350

Recommendations

• Orthogonal polarity graphs and Sidon sets
• Some extremal results on 4-cycles
• The number of 4-cycles in a graph
• Graphs without four-cycles
• Upper bounds on the extremal number of the 4‐cycle

zbMATH Keywords

Sidon set4-cycleTurán number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Other combinatorial number theory (11B75)

Cited In (6)

• Upper and lower bounds on the size of \(B_k[g]\) sets
• Extremal digraphs avoiding an orientation of \(C_4\)
• The number of 4-cycles in a graph
• A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints
• Digraphs that contain at most \(t\) distinct walks of a given length with the same endpoints
• Orthogonal polarity graphs and Sidon sets

This page was built for publication: Sidon sets and graphs without 4-cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477968)